1543年、スペインのルイ・ロペス・デ・ビリャロボス (Ruy Lopez de Villalobos, ?-1546) は、部下のベルナルド・デ・ラ・トーレ (Bernardo de la Torre) に命じて北太平洋を探検させた。トーレの指揮するサン＝ファン (San Juan) 号は、8月26日にフィリピンのミンダナオ島の南端にあるサランガニ島を出航し、北太平洋でいくつかの島を発見している。これがどうも現在の小笠原諸島か火山列島にあたる島々らしい。「らしい」というのは、この航海の内容には不明確な点があり、トーレが見た島が具体的に現在のどの島なのか今ひとつはっきりしないからである。
この時の航海で、トーレは、フィリピンのタンダヤ (Tandaya) 島（不詳、レイテ島またはサマール島か）を出発し、そこから「東方」に「200リーグ」ほど航海した「北緯16度」の地点で一つの「小島」を発見し、「アブレオホス」（Abre Ojos; Abreojos, Abriojos などとも綴る。「眼を開け」の意）と命名している。なお、ここでいう「リーグ」はおそらくスペイン・リーグ、すなわち「レグア」 (legua) であろう。1レグアは約4.2kmだから、200レグアは約840kmとなる。
トーレは、そこからさらに「東」に「26リーグ」（約110km）航行した「北緯16度ないし17度」の地点に「二つの大きな高い島」を発見し、「ラス＝ドス＝ヘルマナス」（Las Dos Hermanas; 「二人姉妹」の意）と命名している。そして、さらに「北東」に船を進め、「300リーグ」（約1260km）進んだ「北緯25度ないし26度」の地点に三つの島を発見し、そのうち一つが火山島であったことから「ロス＝ボルカネス」（Los Volcanes; 「火山」の意）と命名している。タンダヤの港から「500リーグ」（約2100km）の地点である。さらにそこから「北東」に「30リーグ」（約126km）進んだ地点で、10月2日に彼は島をもう一つ発見し、「フォルファナ」 (Forfana) と命名している。サン＝ファン号はそこからさらに「北東」に進み、10月18日に、タンダヤから「700リーグ」（約2940km）、「北緯30度」の地点に達するが、そこから引き返している（大熊良一『小笠原諸島異国船来航記』）。
この記述をそのまま真に受けて地図に書き込んでいくと、ロス＝ボルカネス諸島は火山列島、特に硫黄島とおおむね一致する。この点については特に異論はないようである。フォルファナ島も火山列島かその附近の島とみなすことが可能であろう。だが、その他の島については、アブレオホス島は北緯16度・東経132度附近、ラス＝ドス＝ヘルマノス諸島は北緯16度30分・東経133度附近になってしまう。どちらも沖ノ鳥島のはるか南西のなにもない海域である。
ところが、このアブレオホス島は沖ノ鳥島ではないかとする説がある。この説はかのフランツ・フォン・シーボルト (Philipp Franz Balthasar von Siebold, 1796-1866) が最初に提唱したものらしい。「この島を一番最初に発見したのは、スペインの帆船「サン・ファン号」だった。1543年、全く目立たない沖ノ鳥島に危うく座礁しかかった。そこで、寝ぼけ眼では見落としてしまうと、「Abre ojos（目を開いて見よ）」と命名した」などと書いている文献もある（「サンゴが泣いている 世界でもまれな群落に冷たい日本の海」『AERA』1988年7月26日号）が、何に拠ったものかよくわからない。もし、この説が正しいとすれば沖ノ鳥島の最初の目撃例ということになるのだが、あいにく異論も多く、確定はしていないようである（進士晃「沖の鳥島」）。
例えば、これらの島々をマリアナ諸島の一部とみなし、アブレオホス島をファラリョン＝デ＝メディニラ島（Farallon de Mendinilla; 北緯16度0分・東経146度4分）、ラス＝ドス＝ヘルマノス諸島を同じくアナタハン島（Anatahan; 北緯16度22分・東経145度38分）とサリガン島（Sariguan; 北緯16度43分・東経145度46分）に同定する説もある (D. D. Brand, "Geographical Exploration by the Spaniards", p.123.)。確かに、アブレオホス島が沖ノ鳥島だとすると、ラス＝ドス＝ヘルマナス諸島の説明がうまくつかなくなってしまう。もっとも、火山列島はマリアナ諸島の北東ではなく北北西だから、今度は船の進行方向がおかしくなるのだが。
地図史家の中村拓は、さらに混乱するような解釈をしている。中村は、トーレの発見したアブレオホス島を沖大東島、ラス＝ドス＝ヘルマノス諸島を南北大東島に同定しており（中村拓『御朱印船航海図』, pp.339-341.）、位置関係だけからいえばこの説が最も妥当そうである。ところが同時に中村は、のちにスペイン製海図に登場するアブレオホス島の方は、沖ノ鳥島そのものであるとしているのである（同, pp.371-372.）。
なお、このアブレオホス島は、沖ノ鳥島とは別の疑存島として長らく海図上に残り続けた（Stommel: LOST ISLANDS, p.111. 秋岡武次郎『日本地図作成史』, p.111.）。1924（大正13）年8月には、海軍水路部の測量艦「満洲」が「アブレオジョス疑礁ほか6礁の探礁作業」を行っている（『日本水路史』, p.170）。しかし、どうしても発見できないので、その後海図から消されたらしい。
なんだか邪馬台国論争めいた話になってしまったが、16世紀の技術水準の低さを考えると、トーレの記した距離や方角が大幅に誤っていることは十分に考えられる。トーレは、沖ノ鳥島・小笠原群島・火山列島・南鳥島の第一発見者である可能性が指摘されており、このうち、他はともかく火山列島の第一発見者であることはほぼ定説となっている。だが、彼が沖ノ鳥島の第一発見者であるか否かについては、あいにくと議論の余地があるのである。
1564年、スペイン国王フェリペII世からフィリピン諸島征服の命を受けたミゲル・ロペス・デ・レガスピ（Miguel López de Legazpi, 1505-72）は、メキシコを出発して太平洋を横断し、翌1565年2月、フィリピンに到達し、同地の征服を開始した。フィリピン諸島はその後、300年以上にわたってスペインの支配を受けることになる。
いっぽう、レガスピ隊の首席航海士アンドレス・デ・ウルダネータ（Andrés de Urdaneta, 1498-1568）は、メキシコ・フィリピン間の定期航路を開拓するため、1565年6月1日、サン＝ペドロ号（San Pedro）を率いてフィリピンを出航し、再びアメリカ大陸へと向かった。
この途中、1565年6月21日、サン＝ペドロ号は船のような浅瀬を発見し、「パレセベラ」（Parece Vela; 「帆のような」の意）と名づけた（Sharp, The Discovery of the Pacific Islands, p. 39）。トーレの報告を別にすれば、これが沖ノ鳥島の確実な最初の目撃例と思われる。また、「パレセベラ」（パレセヴェラ）という名前は現在も沖ノ鳥島の別名として広く使われいる。
なお、サン＝ペドロ号は9月18日にメキシコに到達した。ウルダネータの開拓した北太平洋横断航路は、スペインによるフィリピン支配に大きな役割を果たすことになる。
※この項は2005/ 1/11訂正。旧稿では進士晃「沖の鳥島」の誤りをそのまま引き写して、レガスピが発見者であるかのように書いていたが、訂正する。
いずれにせよ、16世紀半ばにはこの珊瑚礁の存在はスペイン人たちに知られだしたようである。遅くとも1639年までには、この珊瑚礁は、スペイン製の海図に「パレセベラ」として登場し始める（秋岡武次郎『日本地図作成史』）。
※なお、『日本国語大辞典』（小学館）をはじめ、少なからぬ文献が「17世紀にスペイン人が発見」と記しているが、これは「17世紀にスペインの海図に現れる」という事実を誤解したものと思われる。
1639年、オランダ東インド会社総督アントニオ・ファン・ディーメン (Antonio van Diemen, 1593-1645) は、探検家マティス・ヘンドリクセン・クアスト (Matthijs Hendricxsen Quast, ?-1641) とアベル・ヤンスゾーン・タスマン (Abel Janszoon Tasman, 1603-59) の二人に、当時日本近海にあるといわれていた「金銀島」の探検を命じ、エンヘル (Engel) 号とフラフト (Graft) 号の二隻を派遣させた。
この探検の途中の7月17日、彼等はこの珊瑚礁を発見し、エンヘル号の名をとって「エンヘルスドローフテ」（Engelsdroogte; 「エンヘル浅瀬」の意）と名づけている（シーボルト『日本』、秋岡武次郎『日本地図作成史』）。彼等はこの島の位置を北緯20度38分・東経135度21分としている。
※ droogte は浅瀬の意。なお、秋岡『日本地図作成史』など多くの文献が誤って「エンヘルスブローフテ」 (Engelsbroogte) としているが、これでは意味が通じない。
一六三九年七月十七日、日曜。朝、風向き、天候、航路、前日に同じ（突風多く、風は西北西。上檣帆に当る風強し。雨も混じる。航路は大体北東）。〔中略〕午後三時ごろ、説教が始まろうとしたとき、マストから下へ向かって、正面前方の北東約一マイル先にひどく波が打ちつけている岩礁があるとの叫び声がした。われわれはすぐさま主帆を降ろして、船尾を南東に向け、右舷帆を用いて約一時間ほど帆走した。こうして、荒れ狂う海を通してその基底部までの全貌が見えた岩礁から離れることができ、航路をふたたび北東にとった。
この岩礁は、われわれの肉眼で見るかぎり、東南東から西北西へ一・五マイルにわたって伸び、南と北の端はひどく先細りになっている。（クアストの日誌、シーボルト『日本』第1巻, pp.183-184 より引用）
なお、彼らは7月21日に、北緯26度38分・東経37度8分の位置に島々を発見し、やはり探検船の名をとって「エンヘル島」「フラフト島」と命名しているが、これは小笠原群島の母島と父島の最初の確実な望見例とされている（大熊良一『小笠原諸島異国船来航記』）。ちなみにタスマンは17世紀有数の大航海家で、ヨーロッパ人としてははじめてタスマニア島・ニュージーランド南島・フィジー諸島などに到達している。また、タスマニア島の名は彼の名に由来する。
1789年9月15日、イギリスの航海家ジョン・ミアーズ (John Meares, 1756?-1809) の部下で、イピゲネイア (Iphigenia) 号の船長ウィリアム・ダグラス (William Douglas) は、北アメリカ大陸から中国へ向かう途中、この珊瑚礁を目撃している。
十時三十分、風下の方に岩礁を見た。それは西北西から東南東の方向に約五マイル延びており、北緑二○度三七分、東経一三六度一〇分にあり、非常に危険である。（Meares, Voyages made in the years 1788 and 1789. シーボルト『日本』第1巻, p.184 より引用）
これ以来、「ダグラス礁」 (Douglas Reef) という別名が付いた（シーボルト『日本』、秋岡武次郎『日本地図作成史』）。この「ダグラス礁」という名前も、「パレセヴェラ」と同様、沖ノ鳥島の別名として広く使われている。
※ミアーズについては「幻想諸島航海記／グランパス島」を参照。
その後、1843年3月にイギリス軍艦マリア (Maria) 号のスプロール (Captain Sproll) がこの珊瑚礁を観察しており（フィンドリー『南洋群島 獨案内』、佐藤孫七「小笠原漁場の漁礁とその発見」）、また1890年にはイギリス船アンフィオン (Amphion) 号が測量を行っている（《本邦島嶼領有関係雑件》）。