Der Vater, Bürgermeister der Stadt Brieg, schickte sein einziges Kind, Heinrich Wuttke, 1829 auf das Maria-Magdalenen-Gymnasium in Breslau. Nach dem Abitur im Jahre 1836 studierte Heinrich Wuttke an der Universität Breslau. Aus dieser Zeit stammte seine Freundschaft mit Hoffmann von Fallersleben. 1838 promovierte er bei Gustav Adolf Harald Stenzel in Breslau mit einer Arbeit über Thukydides. Ab 1841 hielt er Vorlesungen an der Universität Leipzig, nachdem er unter Wilhelm Wachsmuth ebenfalls mit einer Arbeit über Thukydides habilitiert wurde.

1848 wurde er ordentlicher Professor für historische Hilfswissenschaften an der Universität Leipzig. Bemerkenswert hierbei ist, dass er nach dem Erlangen seiner Privatdozentur nie nach einer Beförderung zum außerordentlichen Professor nachgesucht hatte. Seine Beförderung vom Privatdozenten zum ordentlichen Professor resultierte aus einen guten Beziehungen zu dem damaligen sächsischen Kultusminister Ludwig von der Pfordten und dem Tod von Friedrich Christian August Hasse, der den Lehrstuhl für die historischen Hilfswissenschaften in Leipzig innehatte. 1848 war er Mitglied der Frankfurter Nationalversammlung, den gemäßigten Linken und der großdeutschen Richtung zugehörig, eng verbunden mit Robert Blum. Er gehörte zum sogenannten "Württemberger Hof" und dem großdeutschen Verfassungsausschuss an und stimmte gegen Friedrich Wilhelm IV.. Später stand er zeitweise Ferdinand Lassalle nahe.

Er vertrat eine großdeutsche Geschichtsauffassung und war zudem bestrebt, Berufungen von Professoren aus den sog. "Berliner Richtungen" zu behindern. Damit waren Historiker gemeint, die eine dezidiert kleindeutsch-preußische Geschichtsauffassung vertraten. So zum Beispiel war es bei dem Historiker Georg Voigt der Fall. In seinem "historischen Seminar", was eigentlich nur eine seminaristische Übungsgesellschaft gewesen war, saß auch Heinrich von Treitschke als Student. Wuttke war alles in allem ein hervorragender Gelehrter. Das schließlich hatte auch Treitschke anerkannt, auch wenn dessen geschichtlicher Standpunkt dem von Wuttke geradezu entgegengesetzt war.

Wuttke war Mitglied zahlreicher Vereine insbesondere in Leipzig. So war er im Verein für die Geschichte Leipzigs, im Leipziger Schillerverein, im Deutschen Verein, Redeübungsverein, im Leipziger Literatenverein von 1840 u.a.

Für die Universitätsgeschichte war er auch als Reformer hervorgetreten, wenngleich seine Bemühungen um eine Neuregulierung des Gebührenwesens bei Promotionen in Leipzig von den Kollegen zunächst blockiert wurden. Ihm fiel auf, dass die brauchtumsähnliche Verfahrensweise bei den Promotionen keinen Bezug zu den Universitätsstatuten besaßen. Später kam durch Druck des sächsischen Königshauses jedoch eine solche Regelung zustande. Außerdem hatte er zusammen mit anderen Professoren sich für den Erhalt der völkerkundlichen Sammlung von Gustav Friedrich Klemm eingesetzt, welche den Grundstock für das Museum für Völkerkunde in Leipzig bildet. Die Universität hatte er jedoch nicht zum Ankauf der Sammlung zu bewegen vermocht.

Wuttke war Ehrenmitglied der Leipziger Burschenschaft Germania.

Der Nachfolger Wuttkes verbunden mit der Umbenennung des Lehrstuhles für die Historischen Hilfswissenschaften in den für Mittlere und Neuere Geschichte wurde Carl von Noorden.

Wuttkes Sohn war der Volkswirt und Volkskundler Robert Wuttke.