1945 wurde Waldbrunner als Unterstaatssekretär ins Staatsamt für Industrie, Gewerbe, Handel und Verkehr der Provisorischen Staatsregierung Renner berufen und avancierte nach den ersten freien Wahlen der Zweiten Republik – bei welchen er in den Nationalrat gewählt wurde – zum Staatssekretär im Bundesministerium für Vermögenssicherung und Wirtschaftsplanung. Dieses Amt übte er allerdings nur drei Monate lang aus, ehe er im März 1946 als österreichischer Botschafter nach Moskau ging, um dort Wege und Möglichkeiten zur Erlangung eines Staatsvertrages für Österreich auszuloten.

Von 1949 bis 1956 war Karl Waldbrunner Bundesminister für Verkehr und verstaatlichte Betriebe, von 1956 bis 1962 für Verkehr und Elektrizitätswirtschaft, und in dieser Funktion auch Gründungsmitglied der Konferenz europäischer Verkehrsminister (CEMT), deren Präsident er 1960/61 war. Waldbrunner setzte sich massiv für die Idee der Verstaatlichung, v.a. in der Schwerindustrie und auf dem Energiesektor, ein und hatte wesentlichen Anteil an den beiden Verstaatlichungsgesetzen, mit denen 1946 die größten Banken, die Erdöl- und Hüttenindustrie, die wichtigsten Unternehmungen des Bergbaus, der Maschinen- und Metallindustrie, des Fahrzeugbaus, der Elektroindustrie, sowie die DDSG und 1947 auch die Elektrizitätswirtschaft in Staatsbesitz übergeführt wurden. Kommentatoren jener Zeit sprachen gerne vom "Königreich Waldbrunner". Seine Macht und Popularität spiegelten sich auch in seinem innerparteilichen Aufstieg wider.