Karl Lehmann wurde als Sohn des Juraprofessors Karl Lehmann sowie der Malerin und Schriftstellerin Henni Lehmann geboren. Beide Eltern kamen aus jüdischen Familien, die seit Jahrhunderten in Deutschland gelebt hatten, und traten nach ihrer Hochzeit zum Protestantismus über. Ihr Sohn Karl studierte von 1913 bis 1918 Klassische Archäologie in Tübingen, München und Göttingen. 1918 schrieb er sich an der Friedrich-Wilhelms-Universität in Berlin ein, wo er 1922 seine Dissertation über "Die antiken Hafenanlagen des Mittelmeeres" abschloss. Seit 1920 war er mit Elwine Hartleben verheiratet, bis zu seiner Scheidung im Jahr 1944 trug er deshalb den Doppelnamen Lehmann-Hartleben.

Im Februar 1924 habilitierte sich Lehmann-Hartleben in Berlin, wo er bis Ende Oktober 1925 als Privatdozent tätig war. Während seiner Habilitation arbeitete er von März bis Oktober 1923 als Assistent am Archäologischen Institut des Deutschen Reiches der Zweiganstalt Athen. Nach seiner Habilitation hatte er gleichzeitig zu seiner Privatdozentur in Berlin eine Assistentenstelle für Archäologie am Institut des Deutschen Reiches an der Zweiganstalt in Rom und später am Archäologischen Institut der Universität Heidelberg inne.

1929 wurde er als Ordinarius an die Universität Münster berufen, wobei er die meiste Zeit seines Ordinariats im Ausland auf Forschungsreisen verbrachte. Gestützt auf das "Gesetz zur Wiederherstellung des Berufsbeamtentums" entließ die nationalsozialistische Regierung den Archäologen am 7. April 1933 aufgrund seiner jüdischen Herkunft in den vorzeitigen Ruhestand. Lehmann-Hartleben ging zunächst mit seiner Familie nach Rom, bis er 1935 in die USA auswanderte, wo er eine Stelle als Professor am Institute of Fine Arts der New York University fand. Im November 1938 kam Lehmann-Hartleben dem drohenden Rauswurf aus dem Deutschen Archäologischen Institut (DAI), dem er immer noch angehörte, zuvor und erklärte freiwillig seinen Austritt.

Schon in Deutschland hatte sich Lehmann-Hartleben einen Namen als profilierter Kenner der griechischen und römischen Kunst gemacht. Zusätzlich hatte er bei der Erforschung von antiker Architektur und Siedlungsgeschichte wegweisende Akzente gesetzt. Durch seine neue Stelle konnte er jetzt auf der nordgriechischen Insel Samothrake ein vielversprechendes, relativ unerschlossenes Gebiet ausgraben und die Ergebnisse auswerten - mit Unterstützung seiner späteren zweiten Ehefrau Phyllis Williams.

Der Zweite Weltkrieg und der griechische Bürgerkrieg führten zu einer achtjährigen Pause der amerikanischen Ausgrabungen auf Samothraki. Erst ab 1948 konnte Lehmann dort weiterarbeiten, wobei seine Kontakte zu der greichischen Bevölkerung nie abgebrochen waren. Aufgrund seines Engagements wurden ihm 1951 der griechische Phoenix-Orden (Τάγμα του Φοίνικος) und die Ehrenbürgerschaft von Samothrake verliehen.

Alexandra Kankeleit, die Briefe Karl Lehmanns aus der Zeit nach 1945 gesichtet hat, kommt zu dem Schluss, dass dieser sich nach dem Zweiten Weltkrieg ganz als Amerikaner sah. "Die komplette Ablehnung alles Deutschen zeigt sich auch darin, dass er 1945 nicht willens oder in der Lage war, in der ,Tätersprache' zu kommunizieren", stellt sie fest. Die Begeisterung für seine neue Heimat brachte er unter anderem durch zwei Publikationen zu Thomas Jefferson zum Ausdruck. Und doch schreibt er 1959: "Ich lese mit Interesse die Mitteilungen, die ich erhalte und die fast die einzige Informationsquelle bezüglich der Universität, der ich mich in nun ferner Vergangenheit eng verbunden gefühlt habe, sind." Ein Jahr später starb Karl Lehmann an der Folgen einer Krebserkrankung in Basel.

Das Institut für Klassische Archäologie und Christliche Archäologie und das Archäologische Museum haben ihrem einstigen Ordinarius nun den ersten Gesamtkatalog des Museums und eine einmal jährlich stattfindende Vortragsveranstaltung gewidmet.