În jurul anului 1530, lui Nuño Beltrán de Guzmán (președintele Noii Spanie) i s-a spus de către un sclav indian din cele șapte orașe din Cibola, care aveau străzi pavate cu aur și argint.Aproximativ în aceeași perioadă, Hernán Cortés a fost atras de poveștile unei țări minunate departe de nord-vest, populată de femei amazonice și bogată în aur, perle și pietre prețioase.Spaniolii au presupus că aceste locuri pot fi unul și același.O expediție din 1533 a descoperit un golf, cel mai probabil cel din La Paz, înainte de a întâmpina dificultăți și de a se întoarce.Cortés a însoțit expediții în 1534 și 1535 fără a găsi orașul căutat.La 3 mai 1535, Cortés a revendicat „Insula Santa Cruz” (cunoscută acum ca Peninsula Baja California) și a amenajat și fondat orașul care urma să devină La Paz mai târziu în acea primăvară.