Geboren te White Plains, New York. Paul Lehr was een kunstschilder, illustrator en tekenaar. Studeerde aan de Wittenburg University en kreeg les van Stanley Meltzoff aan het Pratt Institute.
Hij verkocht zijn eerste sciencefictionschilderij aan Bantam Books voor de cover van Satellite-E-One van Jeffrey Lloyd Castle. Vervolgens verzorgde hij honderden covers voor sciencefictionboeken en -tijdschriften, evenals non-sf-tijdschriften zoals Life, Time, Saturday Evening Post en Playboy. Naast de beroemde "Grok"-cover voor Stranger in a Strange Land van Robert A. Heinlein, maakte hij covers voor romans van Arthur C. Clarke, Ray Bradbury, Isaac Asimov, H.G. Wells, Frank Herbert en vele anderen.
Hoewel Lehrs vroegste gepubliceerde werken Meltzoffs invloed laten zien, met wie hij kortstondig een studio deelde, ontwikkelde Lehr al snel zijn eigen unieke stem en palet. Zijn beeldtaal, hoewel representatief, deelde abstracte en surrealistische affiniteiten met de kunst van Richard Powers, wiens eerdere succes de weg vrijmaakte voor experimenten in illustratieve kunst. Lehr volgde zijn eigen dictum met originele en briljant gekleurde "futurescapes". Deze bevatten vaak enorme ei-achtige of bolvormige objecten, afgezet tegen grootse maar kale toekomstige landschappen, met de menselijke figuren, indien aanwezig, zo geschaald dat ze in het niet vielen bij hun omgeving. Zijn kunst sierde menige pulpboeken vanaf 1954 tot midden jaren 80, maar ook in bladen als Business Week en Playboy verscheen zijn werk. Lehr werkte in verschillende media, waaronder olieverf, acrylverf (soms in combinatie met olieverf) en gouache, vaak op Masonite of houten panelen, en signeerde elk werk met een geschreven "Lehr".
Zijn dubbelpagina-schilderij van de eerste maanlanding verscheen in de Saturday Evening Post van 8 augustus 1959, tien jaar voor de daadwerkelijke gebeurtenis. Dit originele olieverfschilderij bevindt zich samen met twee andere nu in de permanente collectie van het National Air and Space Museum in het Smithsonian Institute in Washington, DC.
Nadat de genres aan populariteit inboetten ging Lehr verder met het grotere werk. In 1980, 1981 en 1995 werd hij genomineerd voor de Hugo Award for Best Professional Artist, nadat hij in 1979 en 1980 de Analog Award al had gewonnen.
Hij werd jurylid in het eerste jaar van de Illustrators of the Future Contest en bleef dat de rest van zijn leven.
In Nederland gebruikte Meulenhoff enige van zijn prenten voor hun sciencefictionreeks M=SF, bijvoorbeeld voor Jack Vances Blauwe wereld.
Paul Lehr was meer dan alleen een illustrator; hij was een visionair die de manier waarop we sciencefiction en Fantasykunst waarnemen, transformeerde. Met zijn surrealistische meesterwerken transporteerde hij ons naar werelden die onze stoutste dromen te boven gingen, en liet een onuitwisbare indruk achter op het genre. Als we terugkijken op zijn opmerkelijke carrière, kunnen we niet anders dan geïnspireerd raken door de grenzeloze creativiteit en verbeeldingskracht die zijn werk voedden. Uiteindelijk dient Paul Lehrs nalatenschap als een herinnering aan de kracht van kunst om de realiteit te overstijgen en ons mee te nemen op reizen die we nooit voor mogelijk hadden gehouden.
Hij bleef actief tot aan zijn dood in 1998.