La descripción de su descubrimiento se halla en el libro Historia del Almirante, escrito por su hijo Fernando Colón:
Confortándolos Méndez con esta alegría, y mostrándoles la tierra, les dio mucho ánimo, y habiéndoles repartido, para mitigar la sed, una poca agua del barril, bogaron de modo que a la mañana siguiente se hallaron sobre la isla que según hemos dicho, distaba ocho leguas de la Española, y era llamada Navaza.
Haití protestó por la anexión estadounidense de la isla en 1858 y reclamó su soberanía sobre ella.
Cargar guano en medio del fuerte calor tropical, bajo estrictas reglas de trabajo impuestas por los abusivos supervisores blancos, provocó una rebelión en la isla en 1889.
Un barco de guerra estadounidense regresó 18 trabajadores a Baltimore, Maryland, para ser juzgados por asesinato.
La Order of Galilean Fisherman (Orden de los Pescadores Galileos), una sociedad fraternal afroamericana, recaudó dinero para defender a los trabajadores en la corte federal, alegando que éstos atacaron en defensa propia y que los Estados Unidos no tenían jurisdicción completa sobre la isla.
Una petición hecha por Iglesias afroamericanas llegó al presidente Benjamin Harrison, quien decidió conmutar las penas de los trabajadores por prisión.
Desde la Segunda Guerra Mundial, operadores de radio han aterrizado frecuentemente en la isla para difundir programas desde este territorio, al cual le ha sido otorgado estado de país por la American Radio Relay League, asignándole el prefijo indicativo KP1.
Navaza fue agrupada, para propósitos estadísticos, con otras islas guaneras del Caribe que estaban bajo posesión estadounidense bajo el nombre grupal de United States Miscellaneous Caribbean Islands.
La mayoría del territorio consiste de rocas, aunque también crece hierba; además existen árboles y cactus esparcidos por la isla.
Brevifolia), ciruela paloma (Coccoloba diversifolia), lentisco (Sideroxylon foetidissimum) y madera venenosa (Metopium brownei).
Pescadores haitianos transitorios y otras personas acampan en la isla de Navassa, pero por lo demás está deshabitada.
Diversas fuentes informales señalan que Cuba y Jamaica tendrían reivindicaciones durmientes sobre Navaza.
[17][18] Pendiente de una solución a la disputa por la isla entre Haití y los Estados Unidos, Cuba y Jamaica han rehusado las sugerencias del segundo país para establecer límites marítimos con ellos en torno a Navaza.
Otras fuentes oficiosas señalan una supuesta reclamación durmiente por parte de Colombia.