To overcome the shortfall in Alliance strategic sealift capabilities, a High Level Group on Strategic Sealift was established at the NATO Prague Summit in 2002. NATO countries agreed to increase their multinational efforts to reduce the strategic sealift shortfalls for rapidly deployable forces by using a combination of full-time charter and multinational assured access contracts.
In June 2003, at the annual spring meeting of NATO Defence Ministers in Brussels, 11 ministers signed a letter of intent on addressing the sealift shortfalls on behalf of Canada, the Czech Republic, Denmark, France, Greece, Italy, the Netherlands, Norway, Portugal, Spain and Turkey.
Six months later at the autumn meeting of NATO Defence Ministers, nine countries (Canada, Denmark, Hungary, Italy, the Netherlands, Norway, Portugal, Spain and the United Kingdom) signed an agreement to implement the letter of intent, which resulted in the formation of the Multinational Sealift Steering Committee (MSSC)
In February 2004, the consortium, led by Norway, signed a contract with the NATO Support Agency (NSPA) (formerly the NATO Maintenance and Supply Agency (NAMSA)) for the provision of the sealift capability.
The countries pursued an incremental approach, using 2004 as the trial year, with the aim of developing further capacity for subsequent years.
At the 2004 Istanbul Summit, the defence ministers of Bulgaria, Estonia, Latvia, Romania and Slovenia signed a supplementary letter of intent on strategic sealift, where they declared their intent to improve strategic sealift and to provide additional sealift capacity for rapidly deployable forces.