In 2005 Virgin Blue Holdings signed an agreement with the Government of Samoa to operate a joint venture airline.

The announcement came after several months of detailed discussions between the two parties and involved the Samoan government and Virgin Blue joining forces to set up a new company to operate jet routes previously flown by Polynesian Airlines.

The airline was owned by Virgin Australia Holdings (49%), the Government of Samoa (49%) and Grey Investment Group (2%).

[2][3] Pacific Blue Airlines changed its ICAO code from PBI to PBN to prevent air traffic controllers confusing the I for a 1 in flight plans.

[6] In May 2017, the Prime Minister of Samoa, Tuilaepa Aiono Sailele Malielegaoi, wrote to Virgin Australia advising of the government's intention to withdraw from the joint venture.