She was born in Oslo, Norway, and received her education in the United States and Great Britain as well as at the University of Oslo, where she graduated in 1971 with a degree in social sciences. She completed her doctorate at the London School of Economics in 1981.
She began working for the Norwegian Institute of International Affairs (NUPI) in the 1980s, and was among the prime Middle East policy experts, studying ethnical conflicts and peace-keeping operations in the region. During 1994, Heiberg was director of the UN organization for aid to Palestinian refugees UNRWA field office in Jerusalem. From 1995 to 1997 she also held the position as Special Advisor to the Director-General of UNESCO for its Culture for Peace program.
She died from a heart attack.
Her second husband Johan Jørgen Holst, Norwegian Minister of Foreign Affairs, played a central role in Middle East peace efforts. Her sister, Karin Stoltenberg, was a junior minister and the mother of Jens Stoltenberg, the prime minister of Norway.