[2] In 1871, he served as captain of the sloop Isbjørn for Karl Weyprecht and Julius Payer on an expedition to probe the area between Svalbard and Novaya Zemlya for navigability.

Kjeldsen and the Norwegian crew were opposed to this route, as they knew from experience that the ice conditions in that area were typically bad.

[6] In 1874, the Tegetthoff expedition members did end up having to retreat to Novaya Zemlya after their ship was crushed in the ice, but after accidentally rowing past the depot, they decided to continue and rely on the provisions they still had.

[9] In 1882, he worked as ice master for the Austro-Hungarian expedition to Jan Mayen as part of the first International Polar Year.

Ten years later, he had the same role on a Russian expedition to the mouth of the Yenisey under the command of Leonid Dobrotvorskiy [ru].

[10] In 1898, Kjeldsen dropped off Walter Wellman and his expedition at Franz Josef Land as master of the barque Frithjof.

In heavy storms, water entered the engine room through an aperture at the boiler, where bolts had sprung loose.

Arriving in Svalbard, they were forced to wrap the anchor winch in paraffin soaked cloth and set it on fire because it was frozen stiff.

When Kjeldsen inspected the ship and saw very little progress and a constantly drunk engineer, he expressed being weary of working for the American expedition.

[11] In 1903, Kjeldsen, in command of the ship Laura, was tasked with inspecting Baldwin's supply depots in Greenland that Fiala hoped to use on a return trip from the North Pole.

[8] In 1906, Kjeldsen was ice master on the Isle de France, the following year on Princess Alice for Albert I, Prince of Monaco.