Pula’ali’i Nikolao Iuli Tuiteleleapaga Pula es el hijo menor de los doce hijos de Nikolao Iuli Tuiteleleapaga Pula, Sr., de la aldea de Leone, y de Oloalilo Ta’afulisia Simanuali’i Afoa Lutu Molio’o, de las aldeas de Utulei, Fagatogo y Pago Pago. Su padre fue uno de los pioneros del sistema de escuelas públicas de Samoa Americana. Su madre fue una mujer de fe firme que valoraba la honestidad y el trabajo duro. Está casado con Lois Phillips-Pula, Ph.D., profesora jubilada de la Escuela de Enfermería de la Universidad de Georgetown.
Pula’ali’i asistió a escuelas católicas en sus primeros años y más tarde se graduó de la Marist Brothers High School, en Atu’u, Samoa Americana, como el mejor alumno de su promoción en 1974. Continuó sus estudios universitarios en el Menlo College, en Atheron, California, y después en la Brigham Young University, en Provo, Utah. Durante su tercer año en BYU Provo, en 1978, recibió su llamamiento para servir en una misión en Upolu, Savaii y Tutuila. Más tarde retomaría sus estudios en la George Mason University, en Fairfax, Virginia. Al terminar su misión, Pula trabajó durante un breve período en la Oficina de Referencia de la legislatura de Samoa Americana (Fono). En 1981 se trasladó al territorio continental, a Washington D.C., y trabajó durante un año y medio como asistente especial del senador Daniel K. Inouye, de Hawái. Más tarde fue asistente legislativo del congresista Fofo I.F. Sunia, de Samoa Americana, y director de personal del Subcomité de Edificios y Terrenos Públicos del Comité de Obras Públicas y Transporte de la Cámara de Representantes. Durante sus once años en el Capitolio, ocupó distintos cargos tanto en la Cámara de Representantes como en el Senado de EE. UU.; también trabajó para el sargento de armas del Senado. En 1993 se incorporó a la Oficina de Asuntos Insulares (OIA) del Departamento del Interior (DOI) como responsable de políticas para la Mancomunidad de las Islas Marianas del Norte (CNMI), y más tarde pasó a ser director de la División de Políticas.
En la OIA, de 1999 a 2002, desempeñó un papel fundamental como director interino de la oficina. En agosto de 2002, durante la administración del presidente Bush y contra lo que muchos esperaban, Pula Nikolao fue nombrado director de la OIA. El subsecretario adjunto del Interior, David B. Cohen, declaró que, si bien se trataba de un cargo que normalmente se otorga por designación política, se adoptó un enfoque bipartidista debido a la capacidad de Pula para desempeñar la función. Cohen añadió sobre la selección: “Nik goza de gran credibilidad tanto entre los republicanos como entre los demócratas, tanto en el Capitolio como en esta administración”. Nik sería el primer isleño del Pacífico de ascendencia samoana en ser director de Asuntos Insulares del DOI. Durante su gestión, también se desempeñó como subsecretario interino de Asuntos Insulares de enero a septiembre de 2009, y en enero y febrero y en julio de 2014. Fue director de la OIA del DOI durante los veinte años siguientes, de 2002 a 2022, cuando se jubiló como director de carrera (Senior Executive Service) de la Oficina de Asuntos Insulares del Departamento del Interior.