Tatsächlich wurde der Herzog Heinrich in seiner Anwesenheit 919 in Fritzlar zum König gewählt auf Vorschlag des Frankenherzogs Eberhard. Die Versammelten huldigten ihn, die Salbung lehnte Heinrich aber ab. Hierdurch tat er seinen Willen kund, die neue Herrschaft nicht in kirchliche Abhängigkeit geraten zu lassen.

Er lernte aus den Fehlern seiner Vorgänger und versuchte sofort, neue Stammesgewalten für sich zu gewinnen, zumal Schwaben und Bayern der Königserhebung fern blieben. Außerdem hatte Bayern ihren Herzog Arnulf zum König erhoben. Noch 919 erzwang er die Huldigung des Schwabenherzogs Burchard, 921 trotze er gegen eine Reihe von Zugeständnissen den Bayern die Anerkennung seiner Herrschaft ab.