Lehman felt that freelancing was a "very nervous way to make a living", so he began writing copy for a publicity firm that focused on plays and celebrities.
He drew from this experience for the screenplay of the film Sweet Smell of Success (1957), which he co-wrote with playwright Clifford Odets.
[2] In 1958, Metro-Goldwyn-Mayer had hired Hitchcock to make a film called The Wreck of the Mary Deare, based on Hammond Innes' novel of the same name.
The film starred Cary Grant as Roger O. Thornhill, a Madison Avenue advertising executive who is mistaken for a government agent by a group of menacing spies (led by James Mason and Martin Landau).
The writing process took Lehman a year, including several periods of writer's block, as well as a trip to Mount Rushmore to do research for the film's climax.
He was among the few people who initially favored a film adaptation of Edward Albee's play Who's Afraid of Virginia Woolf?.
He persuaded studio executive Jack L. Warner to allow him to take on the project, and the film was a critical sensation, garnering many Academy Award nominations.
He turned down offers to write for Jonathan Demme's The Silence of the Lambs and Brian De Palma's Mission: Impossible.
Lehman completed adaptations for two films that were never made: a screenplay for the Noël Coward classic Hay Fever, and one for a musical version of Zorba the Greek.
Lehman did, however, receive more honorable recognition from the Writers Guild of America than any other screenwriter in film history.