Осторожность Карла была оправданной. С новым Папой следовало считаться. Тебальдо Висконти был лучшей кандидатурой, на которой смогли остановить свой выбор кардиналы. Он был итальянцем, рожденным в Пьяченце, но большую часть своей церковной жизни он провел на севере от Альп во Фландрии и не был замешан в последних политических разногласиях. В момент своего избрания он пребывал в Святой Земле. Тебальдо отправился туда во главе отряда фламандских крестоносцев, выступивших в поход вместе с принцем Эдуардом Английским. Его избрание было для него полнейшей неожиданностью, и Тебальдо не хотелось покидать Палестину. Первое, что он сделал, став Папой, — разослал энциклики, призывающие оказать активную помощь крестоносцам в Сирии, а его последняя проповедь, прочитанная им в Акре прямо перед отплытием в Италию, сводилась к словам: «Если я забуду тебя, о Иерусалим, пусть отсохнет моя правая рука». На протяжении всего понтификата, его страстным желанием оставался крестовый поход в Святую Землю.
Новый Папа высадился в Южной Италии в январе 1272 г. Король Карл встретил его, когда тот проезжал через его королевство, и, несомненно, пытался обсудить с ним политические вопросы. Тебальдо проследовал в Витербо и прибыл туда 10 февраля. Но он хотел, чтобы его восшествие на папский престол проходило в Риме. Карл, как сенатор Рима, поспешил принять его. Тебальд был возведен на папский престол 27 марта под именем Григория X.181
У Григория было достаточно времени, чтобы обдумать свою политику. Через четыре дня после восшествия на престол он издал буллу, призывающую Вселенский церковный собор собраться через два года, 1 мая 1274 г. На соборе должны были обсуждаться три основных вопроса: церковная реформа, объединение Константинопольской церкви с Римской и крестовый поход в Святую Землю. Карл был не очень доволен. Вопрос о церковной реформе мало его касался, разве только это могло ослабить его влияние на Церковь в Сицилийском королевстве, а единственным крестовым походом, к которому он стремился, был поход на Константинополь. Переговоры о добровольном объединении церквей вынудили бы Карла отказаться от своих планов. Но ему было трудно протестовать против столь богоугодного дела. Кроме того, ему нужна была поддержка Папы в Италии. Карл был назначен на пост имперского наместника последним Папой в тот момент, когда императорский трон пустовал, и хотел сохранить за собой этот пост. Содействие Папы было необходимо Карлу, если он хотел сохранить свое влияние на гвельфов по всей Италии. В том случае, если Папа собирался заняться поисками нового императора, а это вскоре показалось вполне вероятным, Карл должен был находиться рядом, чтобы соблюсти свои интересы. Кроме того, он только что ввязался в ссору с Генуей и хотел добиться от Папы помощи.
Отношения Карла с Генуей никогда не были особенно хорошими. Они поссорились очень давно из-за лигурийского побережья, и, хотя генуэзцы получили землю, на которую претендовали, а взамен не оказывали активного сопротивления войскам Карла, двигавшимся через Италию, они ничего не сделали, чтобы ему помочь. Правительство Генуи номинально было гвельф-ским, но гибеллины не были изгнаны из города; к тому же Генуя не вступала в союзы с другими гвельфскими городами. Генуэзцы были возмущены соглашением Карла с бывшим императором Балдуином, поскольку пользовались поддержкой византийцев и боялись ее потерять, особенно когда договор, подписанный в Ви-тербо, давал гарантии только их ненавистным соперникам — венецианцам. Генуя не оказывала поддержки Конрадину, но ведущие генуэзские гибеллины демонстративно вышли приветствовать его, когда он на день остановился в Портофино. В августе 1269 г. правительство Генуи, обеспокоенное укреплением власти Карла в Тоскане и беспокоясь о своих торговых привилегиях в Сицилийском королевстве, в конце концов заключило договор с Карлом и изгнало гибеллинов. Взамен генуэзские купцы получили свое представительство, жилье и таможенные льготы в портах владений Карла.
Договор оказался эфемерным. Генуэзское правительство проявило добрую волю по отношению к французам, предоставив королю Людовику корабли, в которых тот нуждался для Тунисского крестового похода. Когда до Генуи дошла весть о болезнях и невзгодах, постигших крестоносцев, в числе которых были генуэзские моряки, общественное мнение обернулось против правительства. Было невозможно изгнать всех гибеллинов, они были слишком многочисленны, и у их предводителей, семей Спинола и Дориа, было много друзей в городе. 28 октября 1270 г., в день Свв. Симеона и Иуды, начался внезапный мятеж, правительство было свергнуто, и гибеллины вернулись. Уберто Спинола и Уберто Дориа стали капитанами города, опираясь на старейшин коммуны и народа.