Neptune Air was established in 1970 with "Door to door" service from Malaysia and Singapore to different parts of Indonesia. On 21 May 2009 the Malaysian Department of Civil Aviation (DCA) issued an Air Operator Certificate (AOC) to Neptune Air and the airline commenced their operation using a Boeing 737-200F acquired from Tri-MG Intra Asia Airlines. The airline also operates cargo flights for Pos Malaysia from Kuala Lumpur to cities in East Malaysia (Kuching, Miri and Kota Kinabalu).
Despite the large number of aircraft mentioned in their website,most of the aircraft are operated by its partner (Tri-MG Intra Asia Airlines and Airmark Aviation). Neptune Air itself only operating 3 aircraft (with Malaysian registration),which are: