Rok później, w marcu 1991 roku pod kierownictwem ówczesnego ministra sportu Nauru, Vinsona Detenamo, utworzono Nauruański Komitet Olimpijski.
Podczas wizyty prezydenta MKOl-u Juana Antonio Samarancha na Samoa w maju 1994 roku, ówczesny prezydent Nauru Bernard Dowiyogo, odbył wstępne rozmowy, których celem miało być zatwierdzenie NNOC przez MKOl. Prezydent MKOl-u zapewnił, że Nauru stanie się członkiem Międzynarodowego Komitetu Olimpijskiego pod koniec 1994 roku.
4 września 1994 roku podczas 103. sesji tejże organizacji w Paryżu, NNOC oficjalnie został przyjęty jako 196 narodowy komitet olimpijski.
Pierwszy występ Nauruańczyka na igrzyskach olimpijskich miał miejsce już w 1992 roku, jednakże Marcus Stephen nie mógł startować w barwach swojego kraju, ponieważ Nauru nie było wtedy członkiem Międzynarodowego Komitetu Olimpijskiego. Wówczas udzielono mu tymczasowego obywatelstwa Samoa i w jego barwach wystąpił w Barcelonie, gdzie zajął 9. miejsce w kategorii do 59 kilogramów. 4 lata później w Atlancie nauruańscy sportowcy już mogli startować w barwach swojego kraju. Pierwszymi olimpijczykami z Nauru byli Marcus Stephen, Quincy Detenamo i Gerard Garabwan. Największe nadzieje wiązano z występem Stephena, ponieważ ówcześnie był jednym z najlepszych sztangistów na świecie (w swojej kategorii).