Era hijo de Cristóbal Cayetano de Herrera, oriundo de Lanzarote (Islas Canarias), que formó parte del primer Cabildo de Montevideo. Tuvo nueve hermanos.
Estudió en la Universidad Mayor Real y Pontificia San Francisco Xavier de Chuquisaca y fue ordenado allí de sacerdote; pero pronto abandonó los hábitos. Completó sus estudios de derecho en España y regresó a Montevideo en 1801.
En 1802 se casó en Montevideo con Consolación Obes, con la cual tendría un único hijo, Manuel Herrera y Obes.
En 1806 el cabildo de Montevideo lo envió a España a informar sobre las invasiones inglesas y la captura de Buenos Aires.
Permaneció en Madrid casi tres años, en donde obtuvo un éxito relativamente importante en los petitorios que llevaba ante el rey. En 1808 fue compulsivamente electo diputado a las Cortes de Bayona, congreso convocado por Napoleón Bonaparte para representar a las provincias españolas bajo el gobierno de su hermano José. Se mostró como un leal súbdito del Emperador. No había sido elegido por el Virreinato del Río de la Plata, sino por el partido francés de España. Al menos había nacido en el Río de la Plata: otros virreinatos fueron representados por españoles que nunca habían cruzado el océano Atlántico.
Cuando las Cortes fueron disueltas, debido a la Guerra de Independencia Española, regresó a Sudamérica con el cargo de administrador de la Real Hacienda en Huancavelica, Perú, un centro minero clave. Sin embargo, en lugar de ir a Perú, fue destinado a Montevideo, donde lo sorprendió la Revolución de Mayo. Su actitud ante la Revolución fue de apoyo debido a su orientación liberal y afrancesada, aunque el apoyo lo ejerció con cautela y a través de una cuidadosa política, desde su cargo como asesor del Cabildo, que discutía desde mayo de 1810 qué actitud tomar ante los sucesos de Buenos Aires. Mantuvo contactos con los revolucionarios a través de la figura de su amigo el Escribano del Rey en Montevideo, Pedro Feliciano de Cavia, quien estaba fuertemente implicado en el movimiento del lado oriental. Por esa causa fue expulsado de la ciudad por el virrey Francisco Javier de Elío en 1811, se refugió en Buenos Aires.
Apenas llegó a Buenos Aires, su talento político, formación y experiencia anterior parecen haber sido suficientes para ganarle rápidamente altos puestos en la administración revolucionaria. Allí se alió al grupo que había acompañado a Mariano Moreno y participó en los conflictos que llevaron a la caída de la Junta Grande. Fue el secretario de Hacienda del Primer Triunvirato y acompañó la política de Bernardino Rivadavia.
Como secretario de gobierno interino firmó con el enviado portugués Juan Rademaker el armisticio conocido como Tratado Rademaker-Herrera, por el cual las tropas portuguesas abandonaban la Banda Oriental.
Caído el Primer Triunvirato, viajó en misión diplomática al Paraguay donde intentó infructuosamente la reincorporación de esa provincia a las Provincias Unidas del Río de la Plata.
Fue redactor del periódico oficial, La Gazeta de Montevideo, después de la revolución de octubre de 1812, pero sus simpatías por la revolución lo llevaron a renunciar enseguida, pues el periódico estaba destinado a defender la política colonial. Fue miembro de una comisión que preparó la constitución que debía aprobar la Asamblea del Año XIII. La misma nunca fue sancionada.
Fue ministro de gobierno de Gervasio Antonio de Posadas y delegado de Carlos María de Alvear ante el caudillo José Artigas. Fue el redactor de las cartas de Alvear para Lord Strangford y el ministro inglés Castlereagh.
A la caída de Alvear fue exiliado y se unió al grupo antiartiguista de Montevideo. Sus enemigos en Buenos Aires lo acusaron de haber escrito una carta anónima a José Rondeau, que se difundió ampliamente en Buenos Aires, en donde se apoyaba la idea del retorno de las provincias a la tutela de España y Portugal. Él negó obstinadamente haberlo hecho, y jamás se encontraron pruebas que lo vincularan a esa carta. Apoyó la invasión de la Banda Oriental por parte de las tropas del Rey de Portugal, y la toma de su capital. En diciembre de 1817 firmó el tratado por el que se entregaba Montevideo con el comandante invasor, general Carlos Federico Lecor, y poco más tarde, lo recibió bajo palio a su entrada en Montevideo. Éste lo empleó como su secretario personal.
Recibió refugiados en la ciudad a Alvear y José Miguel Carrera, con el apoyo de los cuales organizó una campaña contra el director Juan Martín de Pueyrredón, y los apoyó en sus andanzas de 1820.
Fue el jefe civil del gobierno de la Cisplatina, nombre que dieron los brasileños a la provincia oriental cuando la incorporaron al Brasil. Fue un leal servidor del Imperio del Brasil, y concentró sus esfuerzos en evitar la pérdida de la Cisplatina a manos de la Argentina.
Comenzada la campaña de los Treinta y Tres Orientales, el gobierno de la capital pasó a ser controlado por Lecor; Herrera fue enviado a Río de Janeiro como senador, representando a su provincia.
En 1828 redactó un proyecto de constitución para la nueva República Oriental del Uruguay, y lo presentó al gobierno imperial antes de someterlo a consideración de los uruguayos. Dejó el cargo de senador brasileño mucho después de la pérdida de la Cisplatina, y permaneció al servicio del Imperio del Brasil.
En 1830 el general Fructuoso Rivera asume el gobierno de la recién creada República Oriental del Uruguay. Pero, debido a sus constantes ausencias, el poder real lo ejercía un grupo de allegados llamado popularmente "Los cinco hermanos" entre los que se contaba (además de Nicolás Herrera), José Longinos Ellauri, Lucas Obes, Juan Andrés Gelly, Julián Álvarez y posteriormente Santiago Vázquez.
En este período fue Senador de su país. Murió en Montevideo el 28 de febrero de 1833.