The airline commenced operations as Air Melanesiæ in 1965 as a joint venture between two existing airlines, the British-owned New Hebrides Airways (founded in 1963) and French-owned Société Néo-Hébridaise de Transports Aériens, known as Hebridair (founded 1964). New Hebrides Airways contributed a de Havilland Australia DHA-3 Drover to the operation, while Hebridair provided a Dornier Do 28, however the Do 28 crashed in 1966. By the beginning of the 1970s the airline was controlled by Qantas and British Overseas Airways Corporation via their shareholdings in New Hebrides Airways, and by Union des Transports Aériens which had taken over Hebridair and renamed it Société Francais Air Hebride. In November 1989 the airline was renamed Vanair. In 2004, it merged with Vanuatu's government-owned flag carrier, Air Vanuatu.