Stenzel studierte in Leipzig Theologie und Geschichte, habilitierte sich, nachdem er 1813 als freiwilliger Jäger an den Befreiungskriegen teilgenommen hatte, in Leipzig und 1817 in Berlin.
1820 folgte er einem Ruf als Professor der Geschichte nach Breslau und wurde 1821 Archivar des schlesischen Provinzialarchivs. Vom 18. Mai 1848 bis zum 20. Mai 1849 war er Abgeordneter für Neumarkt in der Nationalversammlung in Frankfurt am Main, wo er der Kaiserdeputation angehörte. 1850 bis 1852 war er Mitglied der preußischen Zweiten Kammer.
Stenzel war auch der Begründer des Historischen Seminars in Breslau. Die Universität Breslau war damit eine der ersten Universitäten, welche über eine solche Einrichtung verfügten. Einer seiner bedeutendsten Schüler war Heinrich Wuttke, mit dem er allerdings nach dessen Promotion infolge eines Streits um dessen Nachweis der Unechtheit des Gierth'schen Tagebuches sich entzweite. Besonders um die Geschichte Schlesiens machte Stenzel sich einen Namen.
1832 wurde er korrespondierendes Mitglied der Historischen Klasse der Bayerischen Akademie der Wissenschaften, 1853 auswärtiges Mitglied.