Kokonaan valtion omistuksessa oleva Air Nauru perustettiin vuonna 14. helmikuuta 1970. Joulukuussa 2005 lentoyhtiön ainoa kone ulosmitattiin velkojen vuoksi. Seuraavana vuonna yhtiö hankki uuden Boeing 737-300:n ja aloitti lokakuussa uudelleen toimintansa nimellä Our Airline. 15. heinäkuuta 2014 yhtiö ilmoitti uudesta nimenvaihdoksesta uudelleenbrändäyksen vuoksi. Uusi nimi Nauru Airlines otettiin käyttöön 1. elokuuta 2014.