La hermana mayor de Catalina, Juana, casará con el hijo del emperador y, fruto de la enemistad de su padre Fernando con Francia, a la benjamina de los Reyes Católicos le tocó ser el enlace de la monarquía hispana con Inglaterra.
El 21 de Mayo de 1501 Catalina se embarca en un viaje hacía una nueva vida, en busca de un destino que quedaría grabado en la historia. Catalina no pasará desapercibida, aunque su popularidad como personaje aumentará en el segundo matrimonio, en Inglaterra. Su madre no pudo acompañarla debido a la enfermedad y a los asuntos del Reino, también su padre andaba ocupado y en este caso se despidió de su “pequeña”, como siempre la denominaba, en una carta. Los encargados de entregarla fueron los condes de Cabra, el arzobispo Fonseca y Pedro Manrique.
El 17 de Agosto, el barco salió desde la Coruña, en ese momento Catalina no sabía que nunca más volvería a su tierra. Tras tres meses de travesía logra llegar a su destino, el viaje se había demorado seis semanas más de lo previsto, debido sobre todo a una tormenta que les sorprendió en mitad de la travesía, pero por suerte pudieron volver a la costa y una vez arreglados los destrozos se pusieron en marcha el 27 de septiembre. Finalmente logran llegar a su destino.
La primera escala antes de llegar se hace en Plymouth el 20 de Octubre de 1501. Vemos a una muchacha envuelta en una nueva tierra, cumpliendo el destino que no había decidido ella, sino sus padres como todas las demás reinas. Pero ella como estamos viendo es diferente, ha tenido una educación no sólo en las labores de una dama sino también a nivel cultural.
En el puerto ante la sorpresa de Catalina no fue el príncipe quien la recibió sino el obispo de Bath. Así como dos embajadores, Pedro de Ayala y Rodrigo González de la Puebla. Entre ambos embajadores existía una fuerte rivalidad en la que Catalina se va a ver involucrada decantándose primero por un Pedro Ayala de aspecto más joven y simpático a primera vista pero menos afín a la causa de los Reyes Católicos.