Cruise & Maritime Voyages was formed in 2009, by parent organisation Cruise & Maritime Services International, after their German based Transocean Tours (for whom they were the UK representative) filed for bankruptcy.
Cruise & Maritime Voyages has positioned itself as "Providing ex-UK 'no fly' cruising holidays aboard smaller and medium sized classic and more traditional style ships". Cruise & Maritime Voyages serves an adult market, with an onboard style of traditional entertainment, dining and rooms using a fleet of older tonnage.
In 2009 the ship was chartered for cruising as the line's first ship and is operated as an adults only (16 and above) vessel, and is marketed at cash short consumers, with multiple departure points in the UK along with exotic itineraries. She is under a five-year charter  with the line, and was transferred in 2009 after previous operator, Transocean Tours filed for bankruptcy.
Joining in November 2013, the ship is sailing for Cruise & Maritime Voyages on a three-year charter, and will sail both northbound and southbound voyages, by way of South Africa, in addition to round-Australia  and Asian itineraries.
It was announced on June 27, 2014 that the ship would be chartered from Portuscale Cruises, to replace the slightly bigger MV Discovery, sometime in 2015. The first voyage sailed 30 nights, from Avonmouth, to the Caribbean, departing Jan. 26.  In June 2016, it was announced that the ship would sail its final season with CMV in 2017. 
It was announced on 3 November 2014 that the ship will be transferred from Ibero Cruises in 2015 and renamed Magellan. The ship received new livery and remains the flagship of the fleet until 2017.
In 2010 the ship was chartered as the second ship of the fleet.Ocean Countess had been chartered as Ruby for Louis Cruise Lines prior to her current charter. Marco Polo was in Tilbury and Ocean Countess in Kingston upon Hull, UK, during the Royal Wedding in 2011. It was also announced on September 7, 2012, that the Ocean Countess will leave the fleet in late 2012, her final cruise was a 13-night Canary Islands & Madeira “Farewell Voyage” concluding in Barcelona instead of returning to Liverpool. She was replaced by the Discovery. Sold for scrap in 2012 after a fire destroyed the ship.
Started in February 2013, the ship sailed for Cruise & Maritime Voyages only in blocks of 249 days, running from May to October, following a joint agreement with All Leisure Group, she replaced the semi-smaller Ocean Countess. Due to old age, She was sold for scrap In October 2014.