Od 1975 służył w marynarce Fidżi, dochodząc do stopni oficerskich. W 1986 jako komandor porucznik brał udział w pracach międzynarodowych sił pokojowychONZ na górze Synaj. W latach 1988–1997 dowódca marynarki Fidżi, od 1997 (do 1998 jako p.o.) szef sztabu generalnego; w kwietniu 1999 zastąpiłEpeli Ganilau na stanowisku dowódcy armii. 29 maja 2000, w ramach akcji przeciwdziałania puczowiGeorge'a Speighta, przejął kontrolę nad państwem i nakłonił do ustąpienia prezydentaKamisese Marę. W lipcu 2000 przekazał władzę nowemu prezydentowi,Josefie Iloilo. W 2001 Bainimarama oraz pułkownikSitiveni Rabuka zostali oskarżeni przez byłego prezydenta Marę oraz odsuniętego również w wyniku wydarzeń z maja 2000 premieraMahendrę Chaudhry’ego o faktyczne inspirowanie puczu Speighta i działanie jedynie w celu przejęcia władzy.
5 grudnia 2006 stanął na czelezamachu stanu, który odsunął od władzy prezydentaJosefa Iloilo oraz rząd premieraLaisenii Qarase. Władzę w kraju przejęła junta wojskowa, na której czele postawiono Bainimaramę, najpierw jako p.o. prezydenta, a od 5 stycznia 2007 jako premiera rządu. 11 kwietnia 2009 prezydentJosefa Iloilo ponownie powołał Franka Bainimaramę na stanowisko szefa rządu.
5 marca 2014 Frank Bainimarama odszedł z armii, przekazując tym samym zwierzchnictwo nad siłami zbrojnymi. Premier deklarował chęć powrotu Fidżi na drogę demokracji i cywilnych rządów[1]. 30 maja 2014 została zarejestrowana partia polityczna Franka Bainimaramy –FijiFirst[2]. Nowa formacja polityczna miała umożliwić lojalistom komodora udział w wyborach parlamentarnych zaplanowanych na 17 września 2014. Partia Bainimaramy wygrała wybory i otrzymała 32 na 50 miejsc w parlamencie.
22 września 2014 prezydentEpeli Nailatikau powołał Franka Bainimaramę na stanowisko premiera nowo sformowanego rządu[3].