Er war der Sohn von Gustav Adolf Harald Stenzel und dessen Ehefrau Maria, geborene Bredow. Nach Besuch des Maria-Magdalenen-Gymnasiums in Breslau war Stenzel von 1849 bis 1860 in der Handelsmarine tätig. Ende der 1850er machte er das Obersteuermanns-Examen. Von 1860 bis 1862 studierte er in Göttingen und Berlin Mathematik und Astronomie. Am 19. April 1862 trat er als Auxiliaroffizier in die Preußische Marine ein, bestand alsbald das Offiziers-Examen und wurde zum Leutnant zur See ernannt. Bereits am 16. November 1863 wurde Stenzel zum Leutnant zur See II. Klasse befördert.
1864 nahm er an Bord der SMS Arcona am Deutsch-Dänischen Krieg teil und wirkte somit am Seegefecht bei Jasmund mit. Während des Deutschen Kriegs erhielt er das Kommando über das Dampfkanonenboot Tiger und bewirkte 1866 die Kapitulation der Stadt Emden sowie die Einnahme der hannoverschen Emsbatterien. 1867 wurde Stenzel zum Kapitänleutnant befördert und arbeite bis 1870 im preußischen Marineministerium. Während des Deutsch-Französischen Krieges war er Stabschef des Oberbefehlshabers des Nordseegeschwaders, Vizeadmiral Eduard von Jachmann. Nach Ende des Krieges wurde Stenzel Offizier im Stab von Admiral Adalbert. Anfang 1872 wirkte er an der Organisierung der Kaiserlichen Admiralität mit. Im Herbst 1872 wurde er zum Korvettenkapitän befördert und erhielt das Kommando über das Kanonenboot Albatroß.
1875 wurde Stenzel Lehrer an der Marineakademie und unterrichtete Seetaktik, Seekriegsgeschichte, Marineorganisation und Marinekunde. Im Dezember 1878 wurde er zum Kapitän zur See befördert. Im Frühjahr 1881 beendete er seine Lehrtätigkeit und wurde Oberwerftdirektor in Wilhelmshaven. Vom Herbst 1885 bis zum Herbst 1886 war Stenzel Chef des Schulgeschwaders und anschließend Inspekteur der Marineartillerie in Wilhelmshaven. Am 18. Oktober 1887 wurde Stenzel aus dem Dienst verabschiedet und am 10. Dezember 1889 zur Disposition gestellt.
Als z.D.-Offizier wurde Stenzel wiederverwendet und wirkte von 1894 bis 1896 als Lehrer an der Marineakademie.