Cristóbal Colón reconoció la isla de Cuba durante su primer viaje de exploración en 1492, aunque no realizó ninguna fundación en ella. La isla estaba habitada por distintos grupos indígenas que vivían de la explotación de la yuca, la recolección de perlas y el comercio con las poblaciones de las islas cercanas. En el año de 1502 los reyes de Castilla, Isabel y Fernando, nombraron a Nicolás de Ovando como gobernador de La Española con el fin de poblar la isla y explorar y colonizar las islas cercanas. Fue por ello que en 1508 se encargó la exploración de Cuba al capitán Sebastián de Ocampo, aunque tampoco fundó ningún establecimiento permanente. Ovando fue sustituido en 1509 en la gobernación por Diego Colón, el hijo de Cristóbal Colón, por una real orden de Fernando el Católico, quien para entonces ostentaba el título de regente del reino de Castilla como consecuencia de la muerte de Isabel la Católica en 1504.

Una de las primeras medidas que tomó el hijo del Almirante fue nombrar a Diego Velázquez, antiguo vecino de La Española, como capitán y le encomendó la misión de conquistar y colonizar la isla de Cuba, bautizada como la Fernandina en honor del rey Fernando. Diego Velázquez organizó una expedición en 1511 en la que participó Hernán Cortés -quien residía en la isla desde 1504- gracias a la cual fundó la ciudad de Santiago de Baracoa, la cual se convirtió en el centro político de la nueva provincia. En ella se estableció la sede episcopal con su cabildo, la casa del gobernador con sus diferentes dependencias de administración y gobierno y el ayuntamiento, del cual Cortés se desempeñó como alcalde durante un par de años. Desde Santiago, partieron nuevas expediciones de colonización gracias a las cuales se fundaron las ciudades de Trinidad y la Habana, centros articuladores de la isla. La vida cotidiana en la isla Fernandina no fue sencilla para sus primeros pobladores castellanos: el calor, la humedad, los huracanes, los mosquitos, las serpientes y los alacranes les generaban molestias continuas.

A los capitanes que participaron en la expedición, como el propio Hernán Cortés o Bartolomé de las Casas, se les concedieron encomiendas en pago de sus servicios. En cumplimiento de las ordenanzas de poblamiento, los castellanos que se establecían en la isla después de la conquista debían de hacerlo acompañado de sus mujeres y su familia y debían pagar al fisco real la mitad de lo que obtuviesen de oro y perlas, así como el quinto real de los productos agropecuarios obtenidos en las tierras que se les repartieran. Una de las primeras pobladoras españolas que conocemos es Catalina Juárez Pacheco, quien había pasado de la Española a la Fernandina como dama de compañía de María de Cuéllar, esposa del gobernador Diego Velázquez. Hernán Cortés y Catalina Juárez contrajeron matrimonio en 1514.

Poco a poco el territorio conquistado se puso en valor y se introdujeron nuevos cultivos como la caña de azúcar, se desarrollaron las plantaciones de maíz y yuca, se trajeron animales procedentes de Castilla como ovejas, vacas, cabras, cerdos -cuya carne se salaba para alimentar a los marineros y tripulantes de las expediciones marítimas- y caballos, los cuales, por su escasez, poseían un alto valor. De igual manera, se fueron asentando especialistas de los distintos oficios artesanales, como herreros, carpinteros y sastres. Debido al clima, muchos de los productos cotidianos que se consumían en Castilla, como el vino o el aceite, debían importarse directamente desde la península ibérica en toneles y barricas y su precio era muy alto: Hernán Cortés señala en sus Cartas, por ejemplo, que una arroba de vino se vendía a dos mil maravedíes o cuatro pesos de oro.  La necesidad de abastecer a las nuevas poblaciones generó un comercio marítimo que permitió que muchos de los nuevos pobladores se enriquecieran rápidamente y con las ganancias obtenidas, podían participar, a su vez, en las expediciones de exploración y conquista de nuevos territorios.  

Los pobladores indígenas, por su parte, sufrieron una suerte adversa. Las fuentes son unánimes en señalar que fueron rápidamente vencidos y reducidos a la esclavitud, violando con ello no sólo el testamento de Isabel la Católica -que les había concedido la condición jurídica de vecinos y, por lo tanto, de hombres libres-, sino también las Leyes de Burgos de 1512 emitidas por el rey Fernando que prohibían la esclavitud indígena. De esta suerte, los naturales fueron obligados a trabajar en las plantaciones de los colonos, a cuidar los ganados, a buscar oro y a extraer perlas, por lo que al cabo de pocos años la población autóctona prácticamente se extinguió y fue necesario importar esclavos africanos.  

La isla Fernandina fue la base de operaciones militares desde las que partieron las expediciones de Francisco Hernández de Córdoba, Juan de Grijalva y Hernán Cortés. A los capitanes españoles correspondía la tarea de comprar los barcos, reunir los bastimentos, la pólvora y las armas necesarias, contratar a los pilotos y marinos, pagar los salarios y reclutar a todos los habitantes de la isla que estuviesen dispuestos a convertirse en soldados y ganar así tierras, honra y fama.