Ada ilk olarak 18 Mart 1522'de Juan Sebastián Elcano tarafından Ferdinand Macellan'ın devrialem filosunun kalan son gemisi tarafından keşfedildi. Elcano, güçlü dalga ve elverişsiz rüzgârlar nedeniyle çıkmaları mümkün olamadığı adaya isim vermemiştir. Hollandalı kaptan Antonio van DiemenHaziran 1633'te vali olarak Java'ya giderken yanından geçtiği adaya gemisinin adı olan Nieuw Amsterdam adını vermiştir. İlerleyen yıllarda Britanyalılar çizdikleri deniz haritalarına Amsterdam ve Saint Paul adalarının adlarını da ilave etmişlerdir. Amsterdam'a ilk ayak basan kişi muhtemelen 1696'da Hollandalı Willem de Vlamingh olmuştur. 28/29 Mart 1792'de Fransız kâşif Joseph Bruny d'Entrecasteaux, kayıp Jean-François de La Pérouse'u aramak için çıktığı seferde adayı ziyaret etmiştir.
1 Temmuz 1843'te, Kaptan Martin Dupeyrat komutasındaki Fransız L'Olympe kıyıya demirledi. Bir kayık ile zorluklarla ulaştığı adaya indi ve Fransa bayrağını çekerek Amsterdam adasını resmen Fransa egemenliğine aldı. Kral, Büyük Britanya ile o zamanki siyasi yakınlaşmayı tehlikeye atmamak için adaya el koyma belgesini onaylamayı reddetti ve Saint Paul Adası'nda konuşlanmış küçük garnizonu geri çekti.[1][2]
Ladislaus Weinek tarafından 1875'te çizilen Amsterdam Adası
Ada, 1857'nin sonlarında Novara Seferi'nin bir parçası olarak bilimsel olarak kısa bir süre keşfedildi. Adanın tamamen Fransa tarafından işgali ancak Ekim 1892'de keşif gemisi La Bourdonnais tarafından gerçekleştirildi ve Ocak 1893'te L'Eure savaş gemisi tarafından onaylandı.
Adayı ilk süreçte kolonileştirme girişimi başarısız oldu. 18 Ocak 1871 - 19 Ağustos 1871'de Fransız Heurtin, eşi, üç çocuğu ve dört hizmetçisiyle adaya yerleşir. Ancak konuksever olmayan ve tarımsal kullanıma da pek izin vermeyen ada, iki hizmetkârın ölümü ve ıssız adada artan yalnızlığı sonucu Heurtin'ler kısa sürede pes etti.[3] Sadece yanlarında getirdikleri sığırlar kaldı, çoğaldı ve onların soyunu sürdüren yavrular 2010 yılına kadar adada kalmaya devam etti.
