A joint venture between Caledonian MacBrayne and The Royal Bank of Scotland, named NorthLink Orkney and Shetland Ferries, won the contract and began operation in October 2002.

A variety of factors, including competition from rival operator Pentland Ferries, the Norse Island Ferries group created by local hauliers concerned about NorthLink's proposed freight pricing, and higher-than-expected operation costs,[2] all contributed to financial difficulties within the company.

[5] This decision was legally challenged in the Court of Session by rival bidder Shetland Line (1984) Limited on the basis that the Scottish Government had allegedly not taken into account that they had scored higher than Serco for their proposed service - suspending the securement of the contract.

[6] On 29 May 2012 however, the court overturned the suspension and Serco was confirmed as the new operator, ending Caledonian MacBrayne's 10 year involvement with Northern Isles ferry services.

[11] In the spring of 2013[12] NorthLink rebranded and launched new on board services such as "sleep pod" reclining seats and a premium lounge.

[16] In February 2020, Paul Wheelhouse, the Scottish Minister for Energy, Connectivity and the Islands, announced that NorthLink's contract would be re-awarded by the end of March.