Gesteund door het succes van zijn optredens, financierde hij zelf opnametijd in een studio om zijn eerste album, Songs by Tom Lehrer (1953) op te nemen. Het kon per post worden besteld. Door mond-tot-mondreclame werd dit album, met daarop het macabere I Hold Your Hand In Mine, het Be Prepared, het ongebruikelijke The Elements en het wiskundige Lobachevsky, een culthit. Lehrer ging vervolgens op tournee en bracht een tweede en derde album uit: More of Tom Lehrer (1959, studio-opname) en An Evening Wasted With Tom Lehrer (1959, live).
Begin jaren 1960 werd de singer-songwriter aangenomen als liedjesschrijver voor That Was The Week That Was, een satirisch televisieprogramma. Veel van zijn liedjes werden openlijk politiek van aard, of speelden in elk geval in op de actualiteiten, met onderwerpen als milieuvervuiling (Pollution), het Tweede Vaticaans Concilie (The Vatican Rag), de verhouding tussen bevolkingsgroepen (National Brotherhood Week), proliferatie (Who's Next?) en de drie huwelijken van de in 1964 overleden Alma Mahler-Werfel (Alma). Lehrer schreef ook een cynisch lied over het ophemelen van Wernher von Braun. Een deel van de liedjes vormt het album That Was The Year That Was (1965).
Lehrer stopte met politieke satire ten tijde van de Vietnamoorlog, een periode die volgens hem te ernstig was om in ironisch-vrolijke liedjes te vatten. Het toekennen van de Nobelprijs voor de Vrede in 1973 aan Henry Kissinger was volgens de satiricus het moment waarop politieke satire door de werkelijkheid achterhaald was geraakt.[1]
In de jaren 1970 legde Lehrer zich met name toe op het doceren van wiskunde en muziektheater. Een enkele keer schreef hij nog een educatief lied voor het kindertelevisieprogramma The Electric Company.
Begin jaren 1980 was Tomfoolery, een revival van zijn liederen in het Londense Criterion Theatre, een verrassend succes.
In 2000 is de cd-box The Remains of Tom Lehrer uitgebracht. Deze bevat live- en studio-opnamen van zijn eerste twee albums, That Was The Year That Was, de liedjes die hij schreef voor The Electric Company, en niet eerder uitgebracht materiaal, zoals het lied That's Mathematics, dat hij schreef ter gelegenheid van het bewijs van de laatste stelling van Fermat door Andrew Wiles. In 2010 bracht Shout! Factory een cd-dvd-combinatie uit, The Tom Lehrer Collection, met daarop - voor het eerst - opnames van liveoptredens van Lehrer.
In 2020, op 92 jarige leeftijd, heeft Lehrer alle teksten en muziek die door hem geschreven zijn vrijgegeven als public domain.[2][3] Daaropvolgend heeft hij dat op 1 november 2022 ook voor alle opnames en optredens gedaan, zodat alle muziek die hij gecomponeerd of uitgevoerd heeft, sindsdien vrij te gebruiken is door iedereen, en direct vanaf zijn eigen website te downloaden is.[4]
Recensies, aangehaald door Lehrer in zijn programma's