He was the son of barrister Axel Heiberg (1875–1952) and his wife Ragnhild Krohg (1879–1947).
In the 1950s, Heiberg designed many buildings for the housing cooperative Oslo Bolig- og Sparelag and Christiania Bank.
He designed also many buildings with Ola Mørk Sandvik until 1968, among them the head office of the Norwegian Ministry of Foreign Affairs in Oslo, the restaurant Annen Etage and the Hotel Continental.
[2] Heiberg's buildings were mostly designed in functionalist style, which he considered "architecture for living people".
However, despite his being a supporter of the communist league Mot Dag in the 1930s, Heiberg opposed the May 1968 revolts, stating that he "with shame had to admit, that [he] was tired of the whole thing".