Mais ce n'était pas le tout que de prendre un vain titre : il fallait en réalité conquérir le trône auquel ce titre était attaché. Charles leva un impôt sur ses vassaux d'Anjou et de Provence, Béatrix vendit tous ses bijoux, à l'exception de son anneau de mariage. Saint-Louis lui-même, désireux de voir son frère occuper ailleurs qu'en France son esprit actif et entreprenant, vint à son aide ; et Charles, grâce à tous ces moyens réunis, aux promesses qu'il fit, et dont son honneur et son courage étaient les garants, parvint à réunir une armée de cinq mille chevaux, quinze mille fantassins et dix mille arbalétriers. Mais, dans la hâte qu'il avait d'arriver à Rome et de remplir dans la ville pontificale l'office de sénateur, qui lui avait été déféré, il prit avec lui mille chevaliers seulement, s'embarqua sur une petite flotte de vingt galères qu'il tenait prête et fit voile pour Ostie, laissant la conduite de son armée à Robert de Béthune, son gendre.
Manfred plaça à l'embouchure du Tibre le comte Guido Novello, qui commandait pour lui en Toscane. Le comte Guido Novello qui gouvernait les galères réunies de Pise et de Sicile, avait une flotte triple de celle de Charles d'Anjou mais Dieu avait décidé que Charles d'Anjou serait roi. Il ouvrit la main et en laissa tomber la tempête ; la tempête faillit jeter la flotte de Charles d'Anjou sur les côtes de Toscane, mais elle éloigna celle de Guido Novello des côtes romaines. Charles d'Anjou poussa en avant avec son vaisseau, aborda seul à Ostie ; puis, se jetant sur une barque avec cinq ou six chevaliers seulement, il remonta le Tibre et vint loger au couvent de Saint-Paul-hors-les-murs, bien plus comme un fugitif que comme un conquérant.
Pendant ce temps, Urbain IV était mort ; mais, poursuivant son projet au delà de sa vie, il avait, avant de mourir, créé une vingtaine de cardinaux auxquels il avait fait jurer de lui donner pour successeur le cardinal de Narbonne, Français comme lui, et de plus sujet immédiat de Charles d'Anjou. Les cardinaux avaient tenu parole, et Guido Fulco, élu presque à l'unanimité pendant le temps même qu'il était en mission près de Charles, était monté sur le trône pontifical en prenant le nom de Clément IV.
Charles avait donc la certitude d'être bien reçu à Rome ; seulement, il n'y voulait faire son entrée qu'avec une suite digne d'un prince tel que lui. Il resta donc au couvent de Saint-Paul-hors-les-murs, au risque d'être enlevé par quelque parti de Gibelins, jusqu'au moment où les galères qu'il avait perdues dans la mer de Toscane arrivèrent à leur tour à Ostie. Charles assembla aussitôt ses chevaliers, et le 24 mai 1265, il fit son entrée dans la capitale du monde chrétien avec le titre solennel de défenseur de l'Eglise.
Pendant ce temps, le reste de l'armée passait les Alpes, descendait dans le Piémont, traversait le Milanais, évitait Florence la gibeline, gagnait Ferrare, et, se recrutant partout des Guelfes qu'elle rencontrait sur son chemin, arrivait devant Rome dans les derniers jours de l'année 1265.
Il était temps. Tous les sacrifices avaient été faits pour l'amener là : Charles d'Anjou et le pape y avaient épuisé leurs trésors ; tous deux manquaient d'argent : il n'y avait donc pas une minute à perdre, il fallait marcher à l'ennemi, et payer les soldats par une victoire.
Charles d'Anjou ne voulut pas même attendre le retour du printemps : il se mit à la tête de son armée, et, dans les premiers jours de février, il s'avança vers Naples par la route de Ferentino