Lehman számos filmet és musicalt jegyzett. 1954-ben kezdte pályafutását, Robert Wise (a West Side Story későbbi rendezője) Executive Suite című filmjével. A fentieken kívül ő írta az Anna és a sziámi király, A díj és a Fekete vasárnap című filmek forgatókönyveit.
Forgatókönyvírásért 4 Oscar-jelölést kapott (Észak-Északnyugat, West Side Story, Nem félünk a farkastól, Sabrina) és kettőt produceri tevékenységéért (Hello, Dolly!, Nem félünk a farkastól). A WGA-díjaira kilencszer jelölték és öt alkalommal meg is kapta. 1972-ben a legrangosabb, a Screen Laurel Award jutott neki. 2001-ben ő lett az első forgatókönyvíró, akit az Akadémia életműdíjjal tüntetett ki.
Ennek átvételekor így szólt a közönséghez: "Az összes forgatókönyvíró nevében veszem át ezt a ritka díjat, de különösen a Writers Guild of America tagjainak nevében, akikkel túlságosan is gyakran maradtunk eddig a névtelenség homályában. Emlékeztetném a kritikusokat és az írókat is, hogy a filmgyártás mindig a forgatókönyvvel kezdődik, és ott is ér véget."