Por su parte, Pedro de Heredia partió de España con la misión de explorar las zonas al sur de la ya establecida provincia de Nueva Andalucía (Santa Marta).