L'histoire des deux îles, Saint-Paul et Amsterdam est liée. L'île Saint-Paul comme l'île d'Amsterdam se trouve au sud de la route entre Le Cap et les îles de la Sonde donc entre l'Europe et les Indes avant l'ouverture du canal de Suez. En 1559, le géographe Evert Gysaerths indique sur un portulan une île par 38°S avec la mention "T.Q. descrobio o nao S. Paulo". Un siècle plus tard, un navigateur hollandais Harwick Claesz de Hillegom aperçoit l'île, dont il estime la latitude à 38°50'S. Il lui donne alors le nom de son navire, "Zeewolf". Le premier débarquement connu semble être celui fait par le navigateur hollandais Willen de Vlaming en 1696 alors à la recherche d'un autre navire hollandais. L'île ou ses parages sont ensuite fréquentés par des pécheurs de l'île Bourbon (actuellement île de la Réunion), des baleiniers américains et anglais et ... des naufragés. En 1793 un navire anglais commandé par lord Macartney en route pour la Chine débarque sur l'île. Il y trouve un marin brestois abandonné par un navire américain. Il dresse une carte de l'île mais la confond avec l'île d'Amsterdam, confusion faite par d'autres navigateurs avant lui.
L'île est redécouverte avec l'île d'Amsterdam par le Polonais Adam Mieroslawski, capitaine du Cygne de Granville en 1842. Le capitaine Mieroslawski a passé son diplôme de capitaine au long cours sous le nom de son frère Pierre Louis Adam Mieroslawski en utilisant le passeport français de ce dernier.
En 1843, Adam Mieroslawski présente au gouverneur de l'île Bourbon (La Réunion), le contre-amiral Bazoche, sa découverte et il propose la prise en possession de ces îles désertes. En absence de navire de guerre en rade, Bazoche fait appel au trois-mâts L'Olympe, commandé par Martin Dupeyart. Le capitaine Dupeyart et son bateau vont ramener Adam Mieroslawski sur ces îles. Le capitaine Mieroslawski est mandaté par le gouverneur de Bourbon, par l'arrêté du 8 juin 1843, pour assumer le commandement de ces îles aussitôt la prise de possession au nom de la France.
Entre-temps le Royaume-Uni conteste cette prise de possession. Pour éviter un problème diplomatique et devant l'intérêt limité de ces îles, la France envoie une dépêche à l'amiral Bazoche demandant le rappel de la garnison. Malgré les ordres, Mieroslawski persiste (il menacera même de hisser le drapeau polonais !) Il commence à négocier avec Bazoche, son ami Adolphe Camin et d'autres interlocuteurs réunionnais pour une exploitation des îles. Ils fondent alors une société par actions en 1845 pour l'exploitation des 2 îles avec création d'établissement sur place. Mais l'entreprise est arrêtée en 1853, avec la mort de son fondateur et le renoncement officiel de sa souveraineté sur l'île par la France.
Durant l'hiver 1857, une expédition scientifique autrichienne embarquée sur la frégate La Novara explore l'île et y étudie la flore, la faune, et la géologie.
En 1871, un navire britannique, le HMS Megaera, qui effectuait un transport de troupes de l'Afrique du Sud vers l'Australie, s'échoue sur l'île. La plupart des 400 personnes qui se trouvaient à bord devront y séjourner jusqu'à trois mois avant d'être récupérées.
Le 23 septembre 1874, des astronomes français y débarquent, arrivés par le navire "Fernand" . Ils viennent observer le passage de Vénus devant le soleil. (Une plaque commémorative qui le rappelle se trouve toujours sur l'île). Lors de cette mission, le géologue et géographe Charles Velain étudie et publie les premières données géologiques des 2 îles. Fin de la mission le 4 janvier 1875. Il semble que c'est à Charles Velain que l'on doit le nom définitif de l'île. Il retrouva la carte de Gysaerths et la mention du nom "Saint-Paul".
En 1892, l'aviso français "La Bourdonnais" reprend possession de l'île pour la France, possession confirmée par le passage d'un second navire de guerre français, "L'Eure", de retour des îles Kerguelen en 1893. Un décret du gouvernement français du 21 novembre 1924 la rattache ainsi que l'île Amsterdam à la province de Tamatave à Madagascar, colonie française à l'époque.
En 1928 une société de pèche "La Langouste Française" crée une usine de mise en conserves à Saint Paul. Cette nouvelle tentative composée de plusieurs français, surtout bretons et d'une centaine de Malgaches va se terminer en désastre en 1931 avec la mort de dizaines de bretons et de la plupart des malgaches, tragédie connue sous le nom des "Oubliés de Saint-Paul".
En 1949, une base scientifique permanente est installée sur l'île Amsterdam. De cette base, des missions ponctuelles sont menées sur l'île Saint-Paul, ces missions allant et venant lors des rotations du Marion Dufresne, navire français qui dessert les TAAF