Hedaya spielte in den 1970er Jahren kleinere Rollen, vorwiegend in den Fernsehfilmen und Fernsehserien. Im Filmdrama Die Verführung des Joe Tynan trat er neben Alan Alda und Meryl Streep auf. In den Jahren 1981 bis 1984 war er in einigen Folgen der Fernsehserie Polizeirevier Hill Street zu sehen. Im Actionfilm Das Phantom-Kommando spielte er neben Arnold Schwarzenegger eine der größeren Rollen. Für seine Gastrolle in der Serie New York Cops – NYPD Blue wurde er im Jahr 1994 für den Emmy Award nominiert. In einer der letzten Episoden der fünften Staffel von Monk mimte er 2006 Jack Monk, den über drei Jahrzehnte verschwundenen Vater des Protagonisten.
In der Komödie Der Club der Teufelinnen spielte Hedaya die Rolle des Morton Cushman, dem untreuen Ehemann von Brenda Cushman, die Bette Midler spielte. Für diese Rolle gewann er 1996 als Mitglied eines Schauspielerensembles den National Board of Review Award. Für seine Rolle im Film Marvins Töchter, in dem er neben Meryl Streep, Leonardo DiCaprio, Diane Keaton und Robert De Niro spielte, wurde er 1997 für den Screen Actors Guild Award nominiert. In der Komödie Lebe lieber ungewöhnlich spielte er die Rolle des Erzengels Gabriel, der zwei Engel losschickt, um Robert Lewis (Ewan McGregor) und Celine Naville (Cameron Diaz) zusammenzubringen. Im Science-Fiction-Film Alien – Die Wiedergeburt mit Sigourney Weaver und Winona Ryder spielte er den Befehlshaber des Raumkreuzers U.S.M. AurigaGeneral Martin Perez. Für die Rolle des US-Präsidenten Nixon in der Komödie Ich liebe Dick wurde er im Jahr 2000 für den Golden Satellite Award nominiert.