Heinrich Albertz wurde am 22. Januar 1915 in Breslau als Sohn eines evangelischen Theologen geboren. Nach strenger Erziehung im konservativen Elternhaus und dem Abitur 1933 in Breslau studierte er Theologie in Breslau, Halle und Berlin. Während des Studiums suchte er Kontakt zu sozialdemokratisch orientierten ausländischen Studenten und hörte illegale Vorlesungen der Bekennenden Kirche, später reiste er als Kurier der Bekennenden Kirche in die Niederlande und nach Dänemark. Albertz arbeitete als Hauslehrer und Pfarrer, wurde mehrfach kurzzeitig festgenommen und entzog sich einer weiteren Verfolgung, indem er sich “freiwillig” zur Wehrmacht meldete. Er bekannte sich auch weiter öffentlich zu dem im Konzentrationslager festgehaltenen Pastor Martin Niemöller, was ihm Festungshaft in Glatz (heute Klodzko) einbrachte.
Nach Kriegsende wurde Albertz die Leitung des städtischen Flüchtlingsamtes in Celle übertragen. Er trat der SPD bei und gehörte seit 1946 dem niedersächsischen Landtag an. 1948 wurde er in die niedersächsische Landesregierung berufen und damit jüngster Minister in Deutschland. Zunächst war er im Kabinett für Flüchtlingsfragen zuständig, 1951 übernahm er das Sozialressort. 1950 wurde er in den Bundesvorstand der SPD gewählt. Von 1950 bis 1965 amtierte er zusätzlich als Vorsitzender der Arbeiterwohlfahrt.
1955 wechselte Albertz als Senatsdirektor in die Senatsverwaltung für Volksbildung nach Berlin. 1959 machte ihn Willy Brandt zum Chef der Senatskanzlei, im Dezember 1961 folgte die Ernennung zum Innensenator. An der Seite Willy Brandts gewann Heinrich Albertz, der seit 1963 auch Bürgermeister und damit stellvertretender Senatschef war, zunehmend an politischem Gewicht. Als Brandt 1966 nach Bonn wechselte, wählte das Berliner Abgeordnetenhaus Albertz am 14. Dezember zum Regierenden Bürgermeister.