Lehrer was born in 1928 to a Jewish family and grew up in Manhattan's Upper East Side. Although he was raised Jewish, Lehrer became an agnostic. He began studying classical piano at the age of seven, but was more interested in the popular music of the age. Eventually, his mother also sent him to a popular-music piano teacher.

Lehrer earned his Bachelor of Arts in mathematics (magna cum laude) from Harvard University in 1946. He received his MA degree the next year, and was inducted into Phi Beta Kappa. He taught classes at MIT, Harvard, Wellesley, and the University of California, Santa Cruz. He remained in Harvard's doctoral program for several years, taking time out for his musical career and to work as a researcher at the Los Alamos Scientific Laboratory. He was drafted into the U.S. Army from 1955 to 1957, working at the National Security Agency(NSA). (Lehrer has stated that he invented the Jell-O Shot during this time, as a means of circumventing liquor restrictions.) These experiences became fodder for songs, e.g., "The Wild West Is Where I Want to Be" and "It Makes a Fellow Proud to Be a Soldier". Interestingly, it was many years before Lehrer publicly revealed having been assigned to the NSA, since the mere 'fact-of' its existence was classified at the time: this left him in the interesting position of implicitly using nuclear weapons work as as cover story for something more sensitive. Despite holding a master's degree in an era when American conscripts often lacked a high school diploma, Lehrer served as an enlisted soldier, achieving the rank of Specialist Third Class (later retitled "Specialist-4" and currently "Specialist"), which he described as being a "corporal without portfolio." In 1960, Lehrer returned to full-time studies at Harvard, but in 1965 gave up on his mathematical dissertation about the subject of modes in statistics, after working on it intermittently for 15 years. From 1962, he taught in the political science department at the Massachusetts Institute of Technology (MIT). In 1972, he joined the faculty of the University of California, Santa Cruz, teaching an introductory course entitled "The Nature of Mathematics" to liberal arts majors--"Math for Tenors", according to Lehrer. He also taught a class in musical theater. He occasionally performed songs in his lectures, primarily those relating to the topic. In 2001, Lehrer taught his last mathematics class (on the topic of infinity) and retired from academia. He has remained in the area, and in 2003 said he still "hangs out" around the University of California, Santa Cruz.

Did Lehrer ever join the military?
He was drafted into the U.S. Army from 1955 to 1957,