The earliest known human inhabitants of the region now known as Nuevo León were a small number of
nomads. They left no written records, so the recorded history of the region begins with the arrival of European
colonists towards the end of the 16th century. The first Europeans to explore what is now Nuevo León, were those of the expedition led by
Alvar Nuñez Cabeza de Vaca, they made an expedition through the
Spanish Florida (La Florida) to the Pacific sea.
 After several failed attempts, a group of settlers, among them several families of converted Jews, arrived on the Mexican coast aboard the Santa Catarina. The Jewish imprint in this colony was mild due to acculturation of conversos to Christianity, but, through the passing of tradition, some Jewish customs are still seen today, such as food preparation and holiday observances. Led by the
Luis Carvajal y de la Cueva they settled in what is now the city of
Monterrey in fulfillment of a commitment made by King
Philip II of Spain: the establishment of the New Kingdom of León (Nuevo Reino de León). Carvajal and his followers, which consisted of more than sixty soldiers and outlaws, were reputed to have made a fortune capturing and selling Indian slaves.
The first years of the colony were difficult for the inhabitants, who were beleaguered by the
Spanish Inquisition, indigenous tribes, and by several floods. The previous settlement founded by Carvajal remained sparsely inhabited and was eventually depopulated. The definitive foundation of Monterrey occurred on September 20, 1596 when Spanish captain
Diego de Montemayor,founded the city of Our lady of Monterrey, "Along with a great mountain and the Santa Lucia
water springs", which had been the name of the village previously founded by Carvajal.