Alrededor de abril de 1533, Heredia fue con la India Catalina a una expedición al norte de la Provincia de Cartagena, y en aquella marcha, logró llegar a su tierra natal, Zamba, y reencontrarse con sus familiares, quienes al verla, la agasajaron y le regalaron oro.