En , Colomb quitte le Portugal, où il vivait depuis 1476, après le rejet de son projet par le roi Jean II.
Il vient chercher des appuis en Castille. Il passe par Palos de la Frontera parce que s'y trouve Violanta Moniz Perestrelo, sœur de son épouse portugaise Filipa (morte vers 1480), mariée à un Aragonais, à qui il veut confier son fils Diego.
D'abord hébergé au monastère de la Rabida, il y entre en contact avec Antonio de Marchena, qui l'encourage
dans son projet et le pousse à aller à la cour des Rois catholiques.
Après avoir effectivement confié Diego à sa belle-sœur, Colomb se rend à la cour à Cordoue. Après avoir réussi à contacter plusieurs hauts personnages, il obtient une première entrevue avec Isabelle et Ferdinand en , à Alcalá de Henares, où Isabelle a accouché en de sa fille Catherine. Son projet, soumis à une commission de l'université de Salamanque, est rejeté en 1487.
Colomb s'établit alors à Cordoue où naît son second fils, hors mariage, Fernand (). C'est l'époque où les Portugais atteignent le cap de Bonne-Espérance (Diogo Cão). Colomb reprend contact avec Jean II, puis avec des nobles andalous de haut rang, notamment le duc de Medinaceli, qui s'affirme prêt à financer son expédition: mais la reine, informée par le duc lui-même, lui répond que «ce sont des affaires royales». Une nouvelle entrevue entre Colomb et Isabelle a lieu au printemps 1489 à Jaen. Mais rien ne se passe ensuite, ni en 1490.
1491
C'est alors que Colomb vient pour la deuxième fois au monastère de la Rabida, où Antonio se trouve encore. Ils reprennent leurs entretiens, avec un nouveau participant, Juan Perez, qui a été antérieurement le confesseur d'Isabelle. Convaincu lui aussi par Colomb, il écrit à la reine, qui le convoque à Santa Fe, à une époque où les Rois catholiques préparent l'assaut final contre Grenade.
Appelé à son tour à la cour, Colomb a une entrevue avec Isabelle en . Une nouvelle commission est réunie et, au terme de négociations assez serrées, Colomb obtient ce qu'il demande: le , les Rois catholiques signent les capitulations de Santa Fe, quatre mois et demi après la chute de Grenade ().
1492
Les préparatifs de l'expédition commencent immédiatement à Palos de la Frontera. Les capitulations sont en effet accompagnées d'une injonction aux autorités de Palos (la ville et les autres juridictions) de fournir à Colomb les navires et les équipages pour son expédition.
Ce voyage vers l'inconnu suscitant peu d'enthousiasme, Antonio de Marchena joue un rôle durant cette phase, en mettant notamment Colomb en relation avec les marins locaux, notamment les frères Pinzon, Martin et Vincent, dont l'accord pour partir avec Colomb suscite d'autres volontaires.
L'escadre (la Nina, la Pinta et la Santa Maria) quitte Palos le et, après une étape aux îles Canaries, jusqu'au , atteint le l'île Guanahani, que Christophe Colomb baptise San Salvador (actuelles Bahamas). C'est le début de la découverte d'un nouveau monde, bien que tous soient persuadés d'avoir atteint les Indes.
Par la suite, dans ses écrits, Christophe Colomb a évoqué le soutien reçu d'Antonio de Marchena durant ces années où beaucoup de gens se moquaient de lui et de son projet.
