Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section «Notes et références».
Après les élections générales du , il défie le Premier ministre sortant, Tomasi Puapua, aux élections législatives. Il devient le plus jeune Premier ministre des Tuvalu à l'âge de 33 ans. Paeniu forme un cabinet composé de cinq membres le .
Les élections générales suivante ont lieu le . Lors de la réunion du Parlement qui suit, les députés partagent également leur soutien à Bikenibeu Paeniu et à l'ancien Premier ministre Tomasi Puapua. En conséquence, le gouverneur général dissout le Parlement le et de nouvelles élections ont eu lieu le . Le Parlement subséquent élit Kamuta Latasi au poste de Premier ministre le , avec une majorité de 7 voix sur 5.
Kamuta Latasi reste Premier ministre jusqu'au . En conséquence du vote d'une motion de censure, Kamuta Latasi démissionne et Bikenibeu Paeniu est élu Premier ministre pour la deuxième fois.
Lors de son second mandat au poste de Premier ministre, une controverse apparaît concernant la conception du drapeau des Tuvalu, duquel son prédécesseur a fait retirer l'Union Jack. Moins ouvertement républicain que Latasi, Paeniu mène avec succès les démarches visant à rétablir le drapeau précédemment utilisé.
Le , le Parlement est dissout et des élections générales se tiennent le . Bikenibeu Paeniu est réélu Premier ministre le . Paeniu demeure Premier ministre jusqu'à sa démission consécutive au vote d'une motion de censure le . Ionatana Ionatana est élu Premier ministre.
Paeniu siège jusqu'en 2006 en tant que membre du Parlement représentant la circonscription de Nukulaelae. En outre, il est ministre des Finances et de la Planification économique dans les cabinets de Koloa Talake, Saufatu Sopoanga et Maatia Toafa.
Paeniu perd son siège au Parlement lors des élections générales de 2006. Il doit relever des défis non seulement de la part de Namoliki Sualiki, indépendant, mais également de ses propres frère et neveu, Iefata et Luke, qui se sont opposés à lui dans sa circonscription. Bikenibeu Paeniu obtient 65 voix (contre 64 pour Luke et 21 pour Iefata), mais Sualiki est élu avec 109 voix.