The earliest known human inhabitants of the region now known as Nuevo León were a small number of Native American 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 Portuguese 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 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.