In 1948, Kahn was sent to a progressive boarding school in Pennsylvania and stayed there until 1952. During that time, her mother pursued her acting dream. Kahn soon began acting herself and performed in a number of school productions. In 1960, she graduated from Martin Van Buren High School in Queens, where she earned a drama scholarship to Hofstra University. At Hofstra, she studied drama, music, and speech therapy. After changing her major a number of times, Kahn graduated from Hofstra in 1964 with a degree in speech therapy.
She appeared in two Broadway musicals in the 1970s: a featured role in Richard Rodgers' 1970 Noah's Ark-themed show Two by Two (her silly waltz "The Golden Ram," capped by a high C, can be heard on the show's cast album) and a leading lady turn as Lily Garland in 1978's On the Twentieth Century. She left (or was fired from) the latter show early in its run, yielding the role to her understudy, Judy Kaye, whose career it launched. She also starred in a 1977 Town Hall revival of She Loves Me (opposite Barry Bostwick and original London cast member Rita Moreno).
Kahn's film debut was in the 1968 short De Düva: The Dove. Her feature debut was as Ryan O'Neal's hysterical fiancée in Peter Bogdanovich's screwball comedy What's Up, Doc? (1972) starring Barbra Streisand. Her film career continued with Paper Moon (1973), for which she was nominated for an Academy Award for Best Supporting Actress. Kahn was cast in the role of Agnes Gooch in the 1974 film Mame, but star Lucille Ball fired Kahn due to artistic differences. (Note: several of Ball's biographies note that Kahn was eager to be released from the role so that she could join the cast of Blazing Saddles, a film about to go into production; whether Kahn was fired or left Mame under mutual agreement is undetermined).
A close succession of Kahn comedies — Blazing Saddles (1974), Young Frankenstein (1974), and High Anxiety (1977) — were all directed by Mel Brooks, who many Hollywood observers claimed was able to bring out the best of Kahn's comic talents. Their last collaboration would be 1981's History of the World, Part I. For Blazing Saddles, she was again nominated for Academy Award for Best Supporting Actress. In the April 2006 issue of Premiere magazine, her performance as Lili von Shtupp in Saddles was selected as #31 on its list of the 100 greatest performances of all time. In 1978, Kahn's comic screen persona reached another peak with Neil Simon's The Cheap Detective, a spoof of Casablanca and The Maltese Falcon directed by Robert Moore. In the film she befuddles Peter Falk's gumshoe with an array of fake identities.
Kahn's roles were primarily comedic rather than dramatic, though the 1970s found her originating roles in two plays that had both elements: 1974's In the Boom Boom Room and 1977's Marco Polo Sings a Solo. After her success in Brooks' films, she played in a number of less successful films in the 1980s (perhaps most memorably as Mrs. White in the 1985 film Clue). She also performed in the movie The Adventure of Sherlock Holmes' Smarter Brother opposite Gene Wilder.
In 1983, she starred in her own short-lived TV sitcom, Oh Madeline, which ended after only one season due to poor ratings. In 1987, Kahn won a Daytime Emmy award for her performance in the ABC After School Special, Wanted: The Perfect Guy.
Late in her career, Kahn returned to the stage, first in Judy Holliday's role in a 1989 revival of Born Yesterday, then as Dr. Gorgeous in Wendy Wasserstein's 1993 play The Sisters Rosensweig, a role that gained her a Tony Award. She played the corrupt mayor (Angela Lansbury's role) in a concert performance of Anyone Can Whistle that was released on CD. She also continued to appear in movies, including the holiday farce Mixed Nuts and a cameo in the 1978 "The Muppet Movie".
In the early 1990s, Kahn recorded a voice for the animated movie The Magic 7. Her most notable role at that time was her recurring role on the sitcom Cosby as Pauline, the eccentric neighbor. She also voiced Gypsy the moth in A Bug's Life. Kahn received some of the best reviews of her career for her Chekhovian turn in the 1999 independent movie Judy Berlin, her final film.