Nauru Airlines (dříve Our Airline) je národní letecká společnost republiky Nauru, která byla založena jako rychlá doprava k sousedním státům Oceánie v období růstu ekonomiky. Společnost provozuje mezinárodní pravidelnou dopravu v pondělí a sobotu z australského města Brisbane, přes Honairu, Nauru, Nadi a Tarawu v jediné letecké lince. V minulosti měla předcházející společnost Air Nauru velkou flotilu letadel, byly provozovány lety na mnoho tichomořských ostrovů a australských měst Melbourne, Brisbane a Sydney. Hlavní základnou tohoto dopravce je Mezinárodní letiště Nauru.
Air Nauru začala létat 14. února 1970 mezi ostrovem Nauru a australským městem Brisbane s letadlem Dassault Falcon 20 (VH-BIZ). V roce 1971 byly zahájeny pravidelné lety s letadlem Fokker F-28 (C2-RN1). V roce 1975 společnost zakoupila Boeing 737-200 (C2-RN3) a 16. června 1976 ještě přikoupila Boeing 727-100.
Na konci 70. let 20. století byla dvě letadla, Boeing 737-727 a 727-200 prodána papuánské letecké společnosti Air Niugini. V roce 1983 společnost vlastnila sedm letadel. Dvě letadla Boeing 727-100 (zápis ze dvou RN7-C2) a pět Boeing 737-200 (C2-RN5, RN6, RN7, RN8 a RN9). Celá populace Nauru čítala v tomto období asi 8 tisíc lidí.
Letecká společnost v období hospodářské krize začala mít špatnou pověst kvůli zrušeným letům a zpožděním. V důsledku toho se dostavila stagnace společnosti, která vyústila v pronajímání a prodávání letadel. Na konci 80. let 20. století kvůli hospodářské krizi musela Air Nauru prodat několik letadel, ponechala si pouze Boeing 737-400 a začala ji spravovat státní správa.
V roce 1990 čelilo Nauru dalším vážným finančním potížím. V roce 1992 byl na společnost Air Nauru vyhlášen konkurz s dluhem kolem 10 miliónů amerických dolarů. Dohoda o pomoci americké společnosti General Electric Capital Corporation selhala, majetek firmy byl obstaven ve prospěch věřitelů a nakonec v roce 2005 zabaven.
Díky finanční podpoře z Tchaj-wanu byla v roce 2006 firma obnovena pod novým názvem Our Airline s reklamním heslem "Let our airline be your airline!" ("Nechť naše letecká společnost je vaše letecká společnost!"). Od té doby provozuje lety na trase z Brisbane na mezinárodní letiště Nauru s mezipřistáním v Honaiře na Šalamounových ostrovech a dál do Tarawy na ostrově Kiribati a Nadi na ostrovech Fidži.