"Hans Hedtoft" was built by Frederikshavns Værft at Frederikshavn in northern Denmark. She was yard number 226, launched on 13 August 1958 and completed on 17 December. She had a double bottom and seven watertight compartments and an armoured bow and stern. She was designed to provide a year-round service between Denmark and Greenland. Like , "Hans Hedtoft" had a riveted hull, a feature which was criticised by Knud Lauritzen, a shipowner. Lauritzen claimed that a riveted hull was not as resistant to ice pressure as a welded hull. "Hans Hedtoft" had the Code Letters and radio callsign OXKA. The ship was named for a former prime minister of Denmark.