"California" is the name of a mythical island in Garci Rodriguez-de-Montalvo's chivalric novel "Las Sergas de Esplandian/ The Adventures of Esplandian" (first published in 1510). This imaginary island is located east of the Indies, i.e. west of the North American continent.

The novel was popular in Spain two decades after Columbus "discovered" America. It was popular because it revived the Greek myth of the Amazons, female warriors who lived with no men. Coincidence or not, Columbus, who always thought that his discovered islands were located just east of the Indies, had written after his very first voyage of 1492 that he had heard of an island populated exclusively by women. Montalvo may have been inspired by Amerindian legends heard by Columbus. Or not. Anyway, the novel ended up inspiring Spanish "conquistadores". Hernan Cortes in person, the conquistador of the Aztec empire, wrote in 1524 to the king of Spain that his men had learned from the natives of an island populated only by women. In 1532 he dispatched ships along the western coast of Nueva Espana (Mexico) to locate the island. In 1535 he personally led another expedition. They started calling it California, the name used in Montalvo's novel. In 1539 he dispatched Francisco de Ulloa, who finally determined that the region they had called "California" was not an island but a peninsula (today's Baja California). Ulloa referred to the Gulf of California as the "Sea of Cortes", but the account of his voyage, published in 1541, is also the first document that uses the name "California".

Spain had little interest in this piece of land and its exploration was left to individuals. In 1542 Juan Cabrillo, one of Cortes' original conquistadores who had become rich by mining gold in Guatemala, built two ships and then ventured north on the west coast of Nueva Espana (Mexico). He arrived at the Island of California and claimed it for Spain, except that he had just "discovered" San Diego Bay, which he named "San Miguel". He ventured further north where presumably no Europeans had ever been and "discovered" Monterey Bay, naming it "Bahia de Los Pinos". His adventure was ended by his untimely death in early 1543. Cabrillo's journey convinced the few who heard of it that there was nothing of value in California. There was nothing in the northwest of America comparable to the great civilizations (and wealth) of the Aztecs and the Incas. The story of Cabrillo's journey was written by another explorer, Andres de Urdaneta, after interviewing the returning sailors.

Sailing westward across the Pacific was easy because of the prevailing winds (the winds that Magellan had taken advantage of in 1521). Sailing eastward was still impossible. In 1564 New Spain's viceroy Luis de Velasco dispatched a fleet led by Miguel Lopez de Legazpi to conquer the archipelago to the west of Mexico, Islas del Poniente, the Philippines, hoping that they would find a way back. A previous mission in 1543 led by Ruy Lopez de Villalobos had reached the Philippines but failed to return. It had convinced Spain that the Pacific Ocean was smaller than it is due to no reliable account from the survivors. Legazpi's mission succeeded and in 1565 Spain began its colonization of the Philippines. The real brain of the voyage had been Andres de Urdaneta, who had now become a missionary friar, and he discovered and plotted the easterly route across the Pacific Ocean from the Philippines back to Acapulco (in about four months). Because of sea currents and winds, his route from Manila to Acapulco went up north, so that the ships first touched land in Cape Mendocino (north of San Francisco), and from there south to Acapulco. That route was important because for the first time gold and silver could be shipped from America to Asia and spices from Asia could be shipped to America. Europe wanted gold and silver from America, and wanted spices, cotton, silk and porcelain from the Far East. It was not possible to trade directly one for the other and avoid at the same time the routes of the Indian Ocean, which were controlled by Muslims and the Portuguese. That started Spain's monopoly of American-Asian trade that lasted two centuries. Basically, Spain had just invented Pacific trade.

Francisco Gali carried out the first trans-Pacific crossing from the Asian mainland to the Americas, sailing from the Portuguese colony of Macau to Acapulco in 1584. In 1587 Pedro de Unamuno carried out the second one, also from Macau to Acapulco. The latter stopped on the California coast,somewhere between Los Angeles and San Francisco, and the crew included Filipino sailors, who were therefore the first Asian people to travel to America, and in particular to California. Ironically, all those Spanish ships that sailed along the coast of California didn't spot the San Francisco Bay.

For the Spaniards, colonization of the East Coast of North America was supposed to be a Portuguese affair. In 1493 the Pope had brokered the Treaty of Tordesillas that mandated a division of the new continent between Spain and Portugal along a specific line (hence the current border of Portuguese-speaking Brazil with its Spanish-speaking neighbors). Britain, of course, didn't recognize this treaty, but Spain did. For them the Atlantic Coast was named after Estevćo Gomes, the Portuguese explorer who had deserted Ferdinand Magellan's expedition in 1521 but then in 1524 had explored the Atlantic Coast all the way north to Terra Nova e Labrador (the land first sighted by Joćo Fernandes Lavrador in 1498), looking for a passage to Asia. The first accurate map of the Atlantic Coast of North America was made by cartographer Diogo Ribeiro for the king of Spain, based on Gomes' journey: the "Padron Real" of 1527. Newfoundland had already been claimed for England in 1497 by explorer John Cabot and in 1583 became England's first colony in North America. On the West Coast, Spain, using the same Papal bull, claimed the Territorio de Nutca (today's Oregon and Washington state) and controlled it from 1789 (when Jose' Martinez built the Fort of San Miguel in today's Vancouver Island) until 1795 (when it finally accepted English rule).

Interest in California was also boosted by Francis Drake's journeys: he reached California in 1579, and Spain was alarmed that the British were approaching Spanish territory. For both commercial and geopolitical reasons, Spain became interested in finally exploring the west coast of Nueva Espana, the largely unknown land which was increasingly known as California. In May 1602 Sebastian Vizcaino, a merchant involved in trade between China and Mexico via the Philippines, was dispatched to explore the coast of California up to Cape Mendocino. After ten months Vizcaino had renamed San Miguel as San Diego and named Monterrey Bay. His crew included the missionary friar Antonio de la Ascension, who kept a daily diary and drew a map in which California is still depicted as an island. For almost two hundred years many maps kept showing California as an island.

Almost a century went by before a European seriously tried to settle in California. In 1697 a Jesuit missionary, Juan Maria de Salvatierra, established the Mision de Nuestra Senora de Loreto Concho', around which the town of Loreto developed, the first permanent settlement of "California" (today's Baja California peninsula in northern Mexico). The Jesuits founded more "missions" in the peninsula. That it was a peninsula and not an island was demonstrated by the Jesuit missionary and cartographer Eusebio Francisco Kino who published his map in 1701. Again, many decades passed before the Spanish government showed any interest in what its subjects were doing in this vast but scarcely populated northwestern region of Nueva Espana. Meanwhile, the Spaniards continued to apply the name "California" for an ever expanding region as they ventured north. The first Chinese to describe the American continent was also the first one to describe Europe: Shouyi Fan aka Luigi Fan, who converted to Catholicism, became a Jesuit and traveled to Rome via Brazil in 1708-09 and wrote "Shen Jian Lu/ Record of Personal Observations" ( 身見錄 ) upon returning to China.