Początki kariery wrestlera (1995 – 2001) Treningi wrestlingu rozpoczął na równi ze swoim kuzynem Eddiem Fatu w szkole zawodowych zapasów prowadzonej przez jego ojca i wuja – Wild Samoans Training Center. Następnie debiutował w 1995 w promocji World Xtreme Wrestling (WXW). Następnie podpisał kontrakt z dużą portorykańską promocją World Wrestling Council (WWC), gdzie występował w tag teamie Samoan Gangsta Party z Samu. Swój pierwszy tytuł zdobył pod koniec grudnia 1995 wygrywając zwakowany IWCCW Tag Team Championship. W 1996 wraz z Samu przeniósł się do Extreme Championship Wrestling (ECW) gdzie prowadzili rywalizację z tag teamami The Gangstas i The Eliminators o tytuły ECW World Tag Team Championship jednak bez sukcesów. W 1997 w WXW gdzie wraz z L.A. Smoothem zdobył drużynowy tytuł WXW Tag Team Championship. W tym samym czasie pojawił się w WWC wygrywając WWC World Tag Team Championship z Tahitim. W grudniu 1997 Matt Anoaʻi i L.A. Smooth sięgnęli po NWL Tag Team Championship utrzymując pasy mistrzowskie do marca 1998NWL Tag Team Championship, cagematch.net, [dostęp 2021-07-24]..