Le vicariat apostolique des îles Marquises a été érigé le 9 mai 1848. Il a été élevé en diocèse de Taiohae le 21 juin 1966. Sa dénomination a été complétée en diocèse de Taiohae ou Tefenuaenata le 31 mai 1974. En marquisien, Tefenuaenata signifierait « la Terre des hommes ».
Le diocèse couvre les six îles habitées des îles Marquises, et il est basé à Taiohae, sur l'île de Nuku Hiva. Ses ordinaires, depuis 1920, sont tous issus de la congrégation des religieux de Picpus (SS.CC.). Avec une population de moins de 10 000 habitants, en très grande majorité catholiques, et seulement 4 prêtres, c'est le plus petit des diocèses français.
Le vicariat apostolique des îles Marquises fut établi le 9 mai 1848 par la bulle papale Apostolicae Servitutis du pape Pie IX, reprenant son territoire du vicariat apostolique d'Océanie orientale (aujourd'hui l'archidiocèse de Papeete).
Le 21 juin 1966, le vicariat apostolique fut élevé au rang de diocèse par la bulle Prophetarum Voces du pape Paul VI et prit le nom de diocèse de Taiohae.
Le 31 mai 1974, le diocèse adopta son nom actuel (Taiohae ou Tefenuaenata) en vertu du décret Summus Pontifex de la Congrégation pour l'évangélisation des peuples.
Les vicaires apostoliques puis évêques de Taiohae
Sont vicaires apostoliques de Taiohae
Joseph Baudichon, vicaire apostolique (1848-1855)
René-Ildefonse Dordillon, vicaire apostolique (1855-1888), également évêque titulaire de Cambysopolis (de)
Rogatien-Joseph Martin, vicaire apostolique (1892-1912)
Pierre-Marie-David Le Cadre, SS.CC, (1920-1952)
Louis-Bertrand Tirilly (de), SS.CC, puis évêque (1953-1966)
Louis-Bertrand Tirilly (de), SS.CC (1966-1970)
Sont évêques de Taiohae ou Tefenuaenata
Hervé Le Cléac'h, SS.CC (1973-1986)
Guy Chevalier, SS.CC (1986-2015),
Pascal Chang-Soï, SS.CC (2015 - ), évêque coadjuteur de 2010 à 2015
Liste des juridictions catholiques d'Océanie