The first sighting of a Spanish boat approaching the island was on October 28, 1492, probably at Baracoa on the eastern point of the island. Christopher Columbus, on his first voyage to the Americas, sailed south from what is now The Bahamas to explore the northeast coast of Cuba and the northern coast of Hispaniola. During a second voyage in 1494, Columbus passed along the south coast of the island, landing at various inlets including what was to become Guantánamo Bay. With the Papal Bull of 1493, Pope Alexander VI commanded Spain to conquer, colonize and convert the Pagans of the New World to Catholicism. On arrival, Columbus observed the Taíno dwellings, describing them as “looking like tents in a camp. All were of palm branches, beautifully constructed”.
The Spanish began to create permanent settlements on the island of Hispaniola, east of Cuba, soon after Columbus's arrival in the Caribbean, but it wasn't until 1509 that the coast of Cuba was fully mapped by Sebastián de Ocampo. In 1511, Diego Velázquez de Cuéllar set out with three ships and an army of 300 men from Hispaniola to form the first Spanish settlement in Cuba, with orders from Spain to conquer the island. The settlement was at Baracoa, but the new settlers were to be greeted with stiff resistance from the local Taíno population. The Taínos were initially organized by cacique (chieftain) Hatuey, who had himself relocated from Hispaniola to escape the brutalities of Spanish rule on that island. After a prolonged guerrilla campaign, Hatuey and successive chieftains were captured and burnt alive, and within three years the Spanish had gained control of the island. In 1514, a settlement was founded in what was to become Havana.
Clergyman Bartolomé de Las Casas observed a number of massacres initiated by the invaders as the Spanish swept over the island, notably the massacre near Manzanillo of the inhabitants of Caonao. According to his account, some three thousand villagers had traveled to Manzanillo to greet the Spanish with loaves, fishes and other foodstuffs and were "without provocation, butchered". The surviving indigenous groups fled to the mountains or the small surrounding islands before being captured and forced into reservations. One such reservation was Guanabacoa, which is today a suburb of Havana.
In 1513, Ferdinand II of Aragon issued a decree establishing the encomienda land settlement system that was to be incorporated throughout the Spanish Americas. Velázquez, who had become Governor of Cuba relocating from Baracoa to Santiago de Cuba, was given the task of apportioning both the land and the indigenous Cubans to groups throughout the new colony. The scheme was not a success, however, as the Cubans either succumbed to diseases brought from Spain such as measles and smallpox, or simply refused to work preferring to slip away into the mountains. Desperate for labor to toil the new agricultural settlements, the Conquistadors sought slaves from surrounding islands and the continental mainland. But these new arrivals followed the indigenous Cubans by also dispersing into the wilderness or suffering a similar fate at the hands of disease.
Despite the difficult relations between the local Cubans and the new Europeans, some cooperation was in evidence. The Spanish were shown by the Native Cubans how to nurture tobacco and consume it in the form of cigars. There were also many unions between the largely male Spanish colonists and indigenous women. Their children were called mestizos, but the Native Cubans called them Guajiro, which translates as "one of us". Although modern day studies have revealed traces of Taíno DNA in individuals throughout Cuba, the population was effectively destroyed as a culture and civilization after 1515. The local Indian population left their mark on the language and placenames of the island, however. The name of Cuba itself and Havana were derived from neo-Taino dialect, and Indian words such as Tobacco, Hurricane and Canoe continue to be used today.