Van 1838 tot 1846 werd Leutemann onderwezen aan de kunstacademie in Leipzig, en studeerde daar in het bijzonder bij Bernhard von Neher, onder wiens leiding hij werkte aan de fresco's in het Slot Weimar en aan de beeldverhalen van de gebrandschilderde ramen van de Stiftskirche in Stuttgart. Sinds 1850 was hij in Leipzig werkzaam als illustrator en schrijver voor tijdschriften, waaronder voor Die Gartenlaube en Illustrirte Zeitung, en maakte foto's voor het Münchener Bilderbogen. Hij illustreerde vele kaarten, maar ook prentenboeken voor kinderen. Als kunstenaar wijdde hij zich vooral aan het tekenen (schetsen) - vooral met betrekking tot klassieke onderwerpen. Dit leidde tot grotere bekendheid van Leutemann in de Gründerzeit. Tot zijn belangrijkste werken behoren de zesendertig staalgravures voor de versie van Van den vos Reynaerde van J. E. Hartmann, die in 1855 in Leipzig verscheen. Leutemann maakte sedert 1850 een reeks van illustraties van dieren en een zoölogischeatlas.
Door zijn kennismaking met Carl Hagenbeck, die voort zou zijn gekomen nadat hij zijn dierenpark had geopend,[1] maakte hij talrijke illustraties van de tentoongestelde dieren van Hagenbeck, die populair werden. Zeldzame dieren en hun aankomst in de dierentuin van Hagenbeck werden gefotografeerd en vervolgens op artistieke wijze ontwikkeld. Deze tekeningen zijn bewaard gebleven in voornamelijk privécollecties.
Leutemann werd blind in 1895. In 1919 werd in Leipzig een herdenkingstentoonstelling opgezet. De werken van Leutemann bevinden zich nu in Berlijn en Leipzig in publieke collecties.
Hans Ries: Illustration und Illustratoren des Kinder- und Jugendbuchs im deutschsprachigen Raum 1871 - 1914. Das Bildangebot der Wilhelmischen Zeit. Geschichte und Ästhetik der Original- und Drucktechniken. Internationales Lexikon der Illustratoren, Bibliographie ihrer Arbeiten in deutschsprachigen Büchern und Zeitschriften, auf Bilderbogen und Wandtafeln. Wenner, Osnabrück, 1992, ISBN 3-87898-329-8
E. Semrau: Leutemann Heinrich. In Klaus Doderer: Lexikon der Kinder- und Jugendliteratur. Personen-, Länder- und Sachartikel zu Geschichte und Gegenwart der Kinder- und Jugendliteratur. Beltz, Weinheim, 1982, ISBN 3-407-56514-3