PNG Air wurde 1987 unter dem Namen Milne Bay Air von John Wild Senior als Charterfluggesellschaft gegründet. Im September 1992 erlangte die Gesellschaft die Regular Public Transport-Lizenz und im März 1997 die Lizenz als Linienfluggesellschaft.[1][2]
Am 22. September 2011 wurde bekannt gegeben, dass die Regierung Papua-Neuguineas aufgrund gewisser Schwierigkeiten der Firmen eine Fusion mit Air Niugini, der größten Fluggesellschaft des Landes, genehmigt hätte.[4] Gewerkschaften sprachen sich dagegen aus[5] und 2016 wurden beide Gesellschaften als gesunde Konkurrenten angesehen.[6]
Ende 2015 wurde Airlines PNG in PNG Air umbenannt.
Ende Mai 2020 wurde bekannt, dass Link PNG eine Übernahme der Fluggesellschaft PNG Air plant. In einer Stellungnahme vom 28. Mai 2020 wehrte sich PNG Air gegen den Übernahmeplan und sagte, dass dieser „ein Monopol schaffen“ würde, mit der Folge, dass „die Preise steigen“ und die Passagiere dann „keine Wahl mehr hätten, wie, wann und wohin sie reisen können“. PNG Air wies auch darauf hin, dass Air Niugini in den letzten Jahren mehr als 15 % des Passagiermarkts an PNG Air verloren habe, die bei jetzt 50 % Marktanteil im Durchschnitt 10 % niedrigere Flugpreise anbiete.[7][8] Die Übernahme wurde 2021 aus Wettbewerbsgründen abgelehnt.[9]
Am 11. Mai 1996 flog eine Britten-Norman BN-2 Islander (Luftfahrzeugkennzeichen P2-ISD) nahe Oumba in ein ansteigendes Tal. Beim Versuch, eine 180°-Wende durchzuführen, streiften die Tragflächen einige Bäume, was zum Absturz der Maschine führte. Ein Passagier wurde getötet, die anderen neun Insassen überlebten.[19]
Am 9. Juli 1996 kollidierte eine de Havilland Canada DHC-6-300 (Luftfahrzeugkennzeichen P2-MBB) beim Anflug auf den Flughafen Mendi in Wolken mit einem Berg. Alle 20 Personen an Bord kamen ums Leben.[20]
Am 29. Juli 2004 wurde mit einer de Havilland Canada DHC-6-300 (Luftfahrzeugkennzeichen P2-MBA) bei schlechter Sicht der Landeanflug auf Ononge abgebrochen und in Richtung des Ausweichflughafens Yongai abgedreht. Dabei streifte die Maschine in einer Höhe von rund 2300 Meter Bäume und stürzte ab. Sie befand sich auf dem wöchentlichen Frachtflug von Port Moresby nach Ononge. Von den drei Besatzungsmitgliedern überlebte nur der Lademeister.[21]
Am 11. August 2009 flog die de Havilland Canada DHC-6-300 (Luftfahrzeugkennzeichen P2-MCB) auf dem Weg von Port Moresby zum Kokoda Track elf Kilometer vor dem Flugplatz in einen Berg. Alle 13 Menschen an Bord kamen ums Leben.[22]
Am 13. Oktober 2011 wurde eine De Havilland DHC-8-100(P2-MCJ) auf dem Weg von Lae nach Madang bei einer Notlandung während des Anflugs weitgehend zerstört. Aus dem Wrack konnten vier Überlebende geborgen werden, darunter auch beide Piloten, 28 Passagiere wurden jedoch getötet (siehe auch Airlines-PNG-Flug 1600).[23][24][25]