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, 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 27th June 2014 that the ship would be chartered from Portuscale Cruises, to replace the slightly bigger MV Discovery, sometime in 2015. The first voyage sailed for 30 nights, from Avonmouth to the Caribbean, departing on 26th January. In June 2016, it was announced that the ship would sail its final season with CMV in 2017. In a U-turn decision, it was announced in February 2017 that Astoria would remain in the CMV fleet for a further season until 2018. She will offer a mini-season from London Tilbury, before being charted by Rivages Du Monde during the summer months.
It was announced on 3rd November 2014 that the ship would be transferred from Ibero Cruises in 2015 and renamed Magellan. The ship received new livery and became the flagship of the fleet until 2017.
On 12th April 2017, P&O Australia Pacific Pearl entered Sembawang shipyard, Singapore to start her transfer to become the new flagship for CMV as Columbus. The ship received the new CMV livery and a light refurbishment.
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 CMV 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 7th September 2012 that the Ocean Countess would 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. An old favourite, she was sold for scrap in 2012 after a fire destroyed the ship.
Commencing in February 2013, the ship sailed for Cruise & Maritime Voyages in blocks of 249 days, running from May to October, following a joint agreement with All Leisure Group. She replaced the slightly smaller Ocean Countess. Due to old age, she was sold for scrap in October 2014.