Fleming ist der Sohn des Stadtpastors Hartenstein. Von seinem Vater erhält Fleming den Unterricht. Anschließßend besucht er dieSchule in Mitteweida 1629 immatrikuliert er sich an der Universität Leipzig für ein Medizinstudium. Dort wird ihm der Magister der Philosophie verliehen.
1633 geht Fleming nach Holstein wo Friedrich von Holstein-Gottorp ihn engagiert als Hofjunker Truchseß seine Gesandtschaft nach Rußland zu begleiten. August 1634 erreicht die Reisegruppe Moskau . Im April 1635 erreicht Fleming wieder Im Oktober der gleichen Jahres reist Fleming dem Herzog nach Persien. Im August 1637 sie Isphahan und bleiben dort bis 1639.
Auf der Rückreise verlobt sich Fleming Reval mit Anna Niehusen einer Tochter des Ältesten der Bürgerschaft .
Auf der Suche nach einer beruflichen erwirbt Fleming 1640 an der Universität Leyden medizinische Doktorwürde und geht nach Hamburg um sich dort als Arzt niederzulassen.
Paul Fleming ist einer der bedeutendsten und der Meisterschüler von Martin Opitz .
Dort stirbt Paul Fleming noch im Jahr 1640 am 25. März.