He completed his military education in 1992, when he met fellow adventurer-to-be Torry Larsen, also of Møre og Romsdal.
Gjeldnes participated in North Pole expeditions in 1997 and 1998, crossed Baffin Island in northern Canada in 1998, and later the same year climbed Mt Aconcagua (6,959 m (22,831 ft)).
In February 2006, Rune Gjeldnes completed "The Longest March", a three-month 4,800-kilometre (3,000 mi) solo ski trek across the South Pole region, becoming the first person to cross that area alone without being resupplied.
The final couple of weeks of the journey had to be made on foot, as Gjeldnes had lost one of his mountain skis off his sled, this before having to descend a glacier of 2,000 m (6,600 ft) ASL in order to reach his destination.
The expedition had a scientific element as Gjeldnes took regular blood samples of himself to be used in studies of the human immune system under extreme conditions.