Kjell Magne Bondevik's first involvement in politics was while at the University of Oslo. There, he became deputy chairman and later chairman of the Norwegian Young Christian Democrats. He was first elected to the Storting in 1973, rising to vice chairman of the Christian People's Party (Christian Democrats) in 1975 and chairman in 1983.
His rise to the prime minister's office was precipitated by events that were largely not in his control. In the 1997 elections, public opinions showed that the Labor Party would easily be again Norway's largest party but prime minister Thorbjørn Jagland pledged to step down if the Labor Party failed to improve on its 1993 total electoral vote of 39.6%. Unexpectedly, the Labor Party did not make it, slipping to 35.2% of the vote and lost two seats—going from 67 to 65— in the Storting. As promised, Jagland stepped down as prime minister, although the Labor Party was the largest party with 65 seats out of 165-seat Parliament. Nevertheless, it went into opposition, a rare situation for a party which has been in office nearly continuously since 1935. Due to Jagland's pledge not to join the next government, the task of creating a workable coalition fell to Bondevik, the leader of the Christian People's Party, as the Norwegian version of Christian Democrats are known.
Bondevik was chosen prime minister on 17 October 1997, and formed a coalition consisting of his Christian People's Party, the Center Party, and the Liberal Party. His three-party coalition government, however, held only 42 of the Storting's 165 seats. In such circumstances, the coalition would have to tread carefully, with the acquiescence of the other party groupings that could easily outvote them. The media quickly dubbed the Bondevik government "the Slalom Coalition" due to its need to zig-zag between the right and the left in order to secure the consensus that would allow Bondevik to govern.
In March 2000, the Bondevik government lost a vote of confidence. The immediate reason was an environmental dispute on the construction of a natural gas power plant. Bondevik argued that Norway should postpone the construction of a new power plant until the introduction of new anti-pollution technology. Both Labor and Conservatives disagreed and argued that Norway should go ahead with new gas-fired power plants under the environmental standards then in place. When Bondevik refused to budge, he was forced to resign.
In February 2000, the Labor leadership appointed Jens Stoltenberg to replace Jagland as the new party leader; Stoltenberg became prime minister in March. He faced a tough task because environmentalists were arrayed against him and he faced opposition from within his own party on environmental issues. (A previous Labor Party leader, Gro Harlem Brundtlandt, a hero for many Labor activists, gained an international reputation for championing the global environment.) Stoltenberg's administration was plagued by
strikes for higher wages that forced an expensive revision of the budget. Instead of spending excess oil monies and cutting taxes, Stoltenberg tried to restructure the public sector and lost support from powerful state-sector trade unions. In the elections of 10 September 2001, Labor won the vote, but dropped from its 35% showing in 1997 to 24%. A center-right coalition composed of Bondevik's Christian People's Party, the Liberals, and the Conservatives, held 62 seats and Bondevik again became prime minister. His government, however, is by definition weak because it can only command 37 percent of the vote in Parliament and has to rely on opposition parties for a parliamentary majority.