Paul Fleming wurde 1609 in Hartenstein (Vogtland) als Sohn des Stadtpastors Abraham Fleming von Hartenstein geboren. Er besuchte von 1622 an die Thomasschule und von 1628 bis 1633 die Universität in Leipzig, wo er sich nach der üblichen gelehrt-philologischen Ausbildung der Medizin zuwandte und sein Studium vorläufig mit dem Magistergrad abschloss (2. 5. 1633). Durch die Vermittlung von Adam Olearius erhielt Fleming die Möglichkeit, an der holsteinischen Gesandtschaft nach Russland und Persien teilzunehmen (1633-39). Berühmt wurde das Unternehmen durch die Reisebeschreibung von Olearius, in der auch Gedichte Flemings enthalten sind. Die Reise wurde durch lange Zwischenaufenthalte unterbrochen, wobei die in Reval 1636 und 1639 biografisch und dichterisch durch die Bekanntschaft mit der Familie des Kaufmanns Heinrich Niehusen besonders bedeutsam wurden. Auf der Rückreise 1639 verlobte sich Fleming mit Anna Niehusen, einer der drei Töchter der Familie, die anagrammatisch verschlüsselt eine wesentliche Rolle in seiner Dichtung spielen. Er reiste dann nach Leiden, wo er 1640 auf Grund einer Disputation über Geschlechtskrankheiten zum Dr. med. promoviert wurde. Er starb 1640 - auf der Rückreise nach Reval - in Hamburg an einer Lungenentzündung.