Comme les autres îles de l'archipel, Fatu Iva fut originellement peuplée par des Polynésiens vraisemblablement arrivés depuis la Polynésie occidentale.
Les rivalités entre les différentes vallées furent fréquentes. L'une d'elle, vers le milieu du XIX siècle, vit s'affronter la tribu des Anainoapa de Hanavave et celle des Tiu d'Omoa. Ces derniers, vaincus, s'enfuirent de l'île sur des radeaux de bambous, et échouèrent aux Tuamotu, sur l'atoll de Napuka, où leurs descendants vivent toujours aujourd'hui. Le sorcier des Tiu, resté à Fatu Iva, dévoila le nom des lieux de la vallée aux vainqueurs (façon d'en reconnaître leur souveraineté), et se fit enterrer vivant, la tête en bas, symbolisant sa défaite et la fin de sa tribu.
Du point de vue des Occidentaux, le premier explorateur à découvrir Fatu Iva fut le navigateur Espagnol Alvaro de Mendaña, le 21 juillet 1595. C'est la première île de l'archipel qu'il vit, mais il ne put y débarquer, ne trouvant pas de mouillage sûr. Il crut à tort avoir trouvé les Îles Salomon, but de son voyage, avant de se rendre compte qu'il venait de découvrir une nouvelle terre. Il donna à l'archipel le nom de « Marquesas de Mendoza », nom du vice-roi du Pérou à l'époque, qui l'avait aidé à lancer son expédition, « voulant ainsi montrer sa gratitude pour l'aide qu'il lui avait donnée ».
En 1937 et 1938, l'anthropologue et aventurier norvégien Thor Heyerdahl et sa femme Liv vécurent un an et demi à Fatu Iva, d'abord à Omoa, puis à Ouia, une vallée aujourd'hui déserte de la côte est de l'île. Il raconta son expérience dans le livre Paa Jakt efter Paradiset (1938), réécrit en 1974 et publié sous le nom de Fatu Hiva, le retour à la nature.
Au début des années 1960, jusqu'en 1966, la plupart des hommes de l'île partirent travailler à Moruroa, dans l'archipel des Tuamotu, à la construction du Centre d'Expérimentation [nucléaire] du Pacifique.
