Sein Vater Carl Friedrich (* 1778, † 1848), war Justizbeamter in Breslau, ab 1809 Kanzler des Gerichts der Freien Standesherrschaft Polnisch-Wartenberg und Neffe des Schriftstellers Gotthold Ephraim Lessing. Seine Mutter Clementine geb. Schwarz (* 1783, † 1821) war Tochter des Regierungskanzlers des Fürsten Hatzfeldt in Trachenberg. Seine Schwester war mit dem Maler Emil Ebers verheiratet. Der künftige Maler verlebte seine Kindheit in dem idyllischen Städtchen Polnisch-Wartenberg (ab 1888: Groß-Wartenberg) und entdeckte hier beim Durchstreifen der schönen Gegend mit ihren riesigen Wäldern seine Liebe zur Natur.
Nach zweijährigem Studium am Katholischen Gymnasium zu Breslau, wo man sein Talent zum Zeichnen entdeckte, ging Lessing im Alter von 14 Jahren nach Berlin und studierte das Baufach an der von Karl Friedrich Schinkel geleiteten Bauakademie. Im Jahre 1823 entschloss er sich, ohne Einwilligung des Vaters, Maler zu werden. Eine entscheidende Rolle spielte dabei seine Reise nach Rügen, die seine Phantasie anregte. Er studierte nun drei Jahre an der Kunstakademie zu Berlin, ging 1826 zusammen mit seinem Freund Wilhelm von Schadow an die Kunstakademie zu Düsseldorf und wurde dort zum Mitbegründer der Düsseldorfer Malerschule. Seinen ersten Erfolg konnte er schon 1825 mit dem Bild Kirchhof mit Leichensteinen und Ruinen im Schnee erreichen, das auf der Berliner Kunstausstellung in diesem Jahr gezeigt wurde, großes Aufsehen erregte und einen hohen Preis erzielte. Der Erfolg versöhnte den Vater mit der Malerkarriere des Sohnes.
In der ersten Periode seiner Tätigkeit malte Lessing melancholische Landschaften in der Nachfolge von Caspar David Friedrich: die Motive waren zerfallene Burgen, vergessene Kirchhöfe, zerklüftete Felsenpartien, die er mit Figuren von Mönchen, Rittern, Räubern, Zigeunern usw. bevölkerte. Andere Motive kamen aus der Dichtung (Lenore, 1832, von dem König Friedrich Wilhelm IV. gekauft), oder aus der Sagenwelt, (Trauerndes Königspaar, 1828, heute in der Eremitage.) Dieser Stil fand viele Nachahmer und artete bei diesen beinahe in Vulgarität aus. Um diese Zeit führte ihn Schadow der Historienmalerei zu und verschaffte ihm einen Auftrag über Wandmalereien beim Grafen von Spee, der den Gartensaal seines Schlosses bei Düsseldorf mit einem Zyklus von Fresken über das Leben Friedrich Barbarossas schmücken wollte. Lessing schuf hier Die Schlacht bei Iconium, entdeckte jedoch bald, dass die Wandmalerei ihm nicht zusagte und überließ den Rest der Arbeiten einem anderen Künstler aus der Düsseldorfer Schule.