Paul Kienzle besuchte die Lateinschule in Neuenbürg und wurde von 1875 bis 1878 in Birkenfeld bei J. Springer als Steinhauer ausgebildet. In den folgenden Jahren arbeitete er im Sommer als Steinhauer und bildete sich ab 1876 im Winterhalbjahr an der Baugewerkschule Stuttgart fort. Nach seiner staatlichen Prüfung zum Baumeister im Jahr 1887 studierte er an der Technischen Hochschule Stuttgart bei Christian Friedrich von Leins Architektur. Kienzle übernahm 1891/1892 für Leins die Bauleitung der Villa Wieland in Ulm. Er ließ sich dort als Architekt nieder und baute überwiegend in Ulm Villen, Wohn- und Geschäftshäuser im Stil des Historismus und später auch im Jugendstil. Im Jahr 1893 erhielt er das Reisestipendium des Königs von Württemberg zum Besuch der Weltausstellung 1893 in Chicago und traf dort den US-amerikanischen Architekten Dankmar Adler (in Büro Adler & Sullivan).
Paul Heinrich Kienzle war verheiratet mit Bertha geb. Remshardt und hatte drei Kinder. Er starb am 26. Januar 1941 in Ulm.
Paul Kienzle war „ein führender Ulmer Architekt jener Zeit“[2].
Außer in Ulm baute Kienzle auch in Birkenfeld, Rastatt, Laichingen, Ostrach und Deggingen.
1891–1892: Bauleitung beim Bau der Villa Wieland in Ulm, Neuthorstraße / Olgastraße (nach Entwurf von Christian Friedrich von Leins; im Zweiten Weltkrieg zerstört; heutiger Standort des Theaters Ulm)[1][2][3][4]
1893–1894: Wohnhaus mit Praxis für den Arzt Dr. Reinhold Frank in Laichingen[5] (später „Haus Hirschle“ bzw. „Kaufhaus Klotz“ genannt; nicht erhalten)
1896: Gebäude Heimstraße 17 in Ulm (unter Denkmalschutz[6])
1897: Wohnhaus für Augustin Wachter in Ulm, Keplerstraße 29 (mit Kepler-Relief)[7][8]
1899–1901: Münsterhotel in Ulm, Bahnhofstraße (im Zweiten Weltkrieg zerstört)[2][3]
1910: Wohnhaus-Gruppe Lichtensteinstraße 5–9 in Ulm[18]
1911–1912: Wohnhaus für den Viehhändler Julius Mohr jr. in Ulm, Zinglerstraße 76[2][3][19]
1910–1911: Erweiterungsbau des Schulhauses in Birkenfeld[20] (nach Gutachten durch Paul Bonatz[21]; heute Friedrich-Silcher-Schule)
Thomas Vogel: Kunst- und Kulturdenkmale im Alb-Donau-Kreis und in Ulm. Theiss, Stuttgart 2005, ISBN 3-8062-1901-X.
Uwe Heinloth, Reintraut Semmler: Auf den Spuren von Jugendstil und Historismus in Ulm. Klemm & Oelschläger, Münster / Ulm 2010, ISBN 978-3-932577-93-2.
Hans-Joachim Albinus, Detlef Suckrau: Reminiszenzen an Johannes Keplers Aufenthalt in Ulm 1626-1627. Neues, Merkwürdiges und ungelöste Rätsel. In: Ulm und Oberschwaben, Band 61 (2019), S. 175–211 (Kapitel 6 zum Wohnhaus Keplerstraße 29).
Hans-Joachim Albinus, Detlef Suckrau: Johannes Kepler in Ulm Revisited. New Aspects of Old Known Facts. A Tribute in Honor of Kepler's 450th Birthday. In: The Mathematical Intelligencer, Vol. 43 (2021), No. 1, p. 64–77 (Kapitel "Kepler Relief at the Residential Building Keplerstraße 29").