[1] 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 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.
Her second husband Johan Jørgen Holst, Norwegian Minister of Foreign Affairs, played a central role in Middle East peace efforts.