The first known mention of the legend of the "Island of California" was in the 1510 romance novel Las sergas de Esplandián by Garci Rodríguez de Montalvo—the sequel to Montalvo's more famous tales of Amadis de Gaula, father of Esplandian. He described the island in this passage:

Know, that on the right hand of the Indies there is an island called California very close to the side of the Terrestrial Paradise; and it is peopled by black women, without any man among them, for they live in the manner of Amazons.

It is probable that this description prompted early explorers to misidentify the Baja California peninsula as the island in these legends.

In 1533, Fortún Ximénez, a mutineer on an exploring expedition sent by Hernán Cortés, discovered the southern portion of Baja California, around La Paz. Cortés himself followed up on the discovery with an expedition to La Paz, but the settlement had to be abandoned soon afterwards. Cortés' limited information on southern Baja California apparently led to the naming of the region after the legendary California and to an initial but short-lived assumption that it was a large island.

In 1539, Cortés sent the navigator Francisco de Ulloa northward along the Gulf and Pacific coasts of Baja California. Ulloa reached the mouth of the Colorado River at the head of the Gulf, which seemed to prove that the region was a peninsula rather than an island. An expedition under Hernando de Alarcón ascended the lower Colorado River and confirmed Ulloa's finding. Maps published subsequently in Europe during the 16th century, including those by Gerardus Mercator and Abraham Ortelius, correctly showed California as a peninsula.

Despite this evidence, however, the depiction of California as an island revived in the early 17th century. One contributing factor may have been the second voyage of Juan de Fuca in 1592. Fuca claimed to have explored the western coast of North America and to have found a large opening that possibly connected to the Atlantic Ocean —- the legendary Northwest Passage. Fuca's claim remains controversial because there is only one surviving written account of it found, his account as related to an Englishman, Michael Locke. Nonetheless, this account claims Fuca found a large strait, with a large island at its mouth, at around 47° north latitude. The Strait of Juan de Fuca is in fact at around 48° N, as is the southern tip of the large island now called Vancouver Island, while the northern reach of the Gulf of California terminates much farther south, at about 31° N. It is possible that explorers and mapmakers in the 17th century could have confused the two (if in fact they were aware of Fuca's voyage), and in any case further exploration was inevitable. Indeed the famed British explorer James Cook barely missed the Strait of Juan de Fuca in March 1778, almost 200 years later. Cook even named Cape Flattery (at the northwest tip of modern Washington state) which is at the mouth of the strait, and instead stopped in Nootka Sound just off the west coast of Vancouver Island at about 49° N. His account states "we saw nothing like [the Strait of Juan de Fuca]; nor is there the least probability that ever any such thing existed."[1] However, Cook describes some bad weather in his account around this time, and did continue on to map most of the outer Pacific coastline of North America from modern day northern California to the Bering Strait in Alaska on the same voyage.

Reports from Oñate's expedition reached Antonio de la Ascención, a Carmelite friar who had participated in Sebastián Vizcaíno's explorations of the west coast of California in 1602 and 1603. Ascención was a tireless propagandist in favor of Spanish settlement in California, and his later writings referred to the region as an island. As older maps confirm, Spanish authorities and local residents were well aware where the actual northern terminus of the Gulf of California lay, but by extending the coastline north past Cape Mendocino and eventually even into Puget Sound, Drake's claim of Nova Albion for England (1579) could be invalidated by the priority of Cortes' claim (1533).

Shortly thereafter an overland expedition was led by the founding governor of New Mexico, Juan de Oñate. The expedition descended the Colorado River in 1604 and 1605, and the official report claimed that from a vantage point the participants could see better where the Gulf of California continued off to the northwest (presumably behind in the Sierra Cucapá into the Laguna Macuata Basin). Subsequently, the first known reappearance of the Island of California on a map dates to 1622 in a map by Michiel Colijn of Amsterdam. The image became the standard for many later maps throughout the 17th century and intermittently into the 18th century. Previous maps show the Gulf terminating in its correct location. The stretch of the Gulf between its actual terminus and Juan de Fuca's strait was written Mare Vermexo ("Sea of See Better") on later maps drawn from Spanish sources. (At the time, Dutch map-makers lived under Spanish control.)

The Jesuit missionary and cartographer Eusebio Francisco Kino revived the fact that Baja California was a peninsula. While studying in Europe, Kino had accepted the insularity of California, but when he reached Mexico he began to have doubts. He made a series of overland expeditions from northern Sonora to areas within or near the Colorado River's delta in 1698–1706, in part to provide a practical route between the Jesuits' missions in Sonoran and Baja California but also to resolve the geographical question. Kino satisfied himself that a land connection must exist, and the 18th century Jesuits generally followed his example. However, Juan Mateo Manje, a military companion on several of Kino's treks, expressed scepticism; European cartographers remained divided on the question.

Jesuit missionary-explorers in Baja California who attempted to lay the issue finally to rest included Juan de Ugarte (1721), Ferdinand Konšcak (1746), and Wenceslaus Linck (1766). The matter was settled beyond all dispute when the expeditions of Juan Bautista de Anza traveled between Sonora and the west coast of California in the period 1774–1776