La jeune femme arrive à Vitoria vêtue d'un costume masculin mal ajusté et se met au service d'un professeur d'université, qu'elle abandonne par la suite. Elle se rend à Valladolid, en tant que page du secrétaire du roi, Juan de Idiáquez, qu'elle sert pendant quelques mois jusqu'à ce que, un beau jour, son père fasse son apparition chez Idiáquez, qui était son ami. Catalina s'enfuit de peur d'être découverte. On la retrouve ensuite à Bilbao où elle passe un mois en prison pour avoir blessé d'un coup de pierre un individu qui se moquait d'elle. Elle passe ensuite deux ans de sa vie à Estella, au service d’un chevalier nommé Alonso de Arellano. Vers 1602 ou 1603, « sans autre raison que mon bon plaisir », elle retourne à Saint-Sébastien et se rend à la messe au couvent d’où elle s’était enfuie, sachant que, selon toute probabilité et comme cela se produit par la suite, elle pourra y voir ses parents et ses frères sans être découverte. Il semble que dans cette ville, elle ait servi pendant trois mois sa tante Ursula de Zarauz, qui ne la reconnaît pas. Mais Erauso ressent cette envie que tant de Basques de son époque ont connue : l’appel des Indes. Le lundi saint de 1603, elle embarque, comme mousse sur le galion d’un de ses oncles, Esteban Eguiño, en direction des Indes.