Но периоды мирных отношений чередовались с военными стычками. В 1034 году пизанцы напали на алжирский город Бона. В 1063–1064 годах был предпринят набег на порт Палермо: добыча от него пошла на строительство собора, в основе форм и пропорций которого, как и расположенного рядом великолепного Баптистерия Бонанно, лежат точные измерения храмов Гроба Господня в Иерусалиме и Рождества Христова в Вифлееме. Наконец, в 1087 году произошло нападение на порт ал-Махдия, важность которого историки долгое время недооценивали по вине некоего злонамеренного скандинавского хрониста, близкого к Рожеру I. Завоевателю Сицилии не нравились многочисленные военные предприятия против мусульман, которые могли испортить его добрососедские отношения с Египтом и североафриканскими правителями: он даже отклонил предложение Пизы участвовать в захвате ал-Махдии. Сегодня, напротив, значение этой экспедиции оценивается в полной мере. Это был не просто ответ на какую-либо выходку со стороны торговцев или пиратов: ал-Махдия вместе с Мазарой была для мусульман важным промежуточным пунктом на морских торговых путях, связывающих Альмерию и порты Нила. Уже из этого понятно, сколь высоки были ставки.
Действительно, экспедиция готовилась долго и тщательно, в ней было задействовано внушительное количество кораблей и людей. Кроме того, Папа Виктор II предоставил ее участникам отпущение грехов — видимо, аналогичное тому, которое дал Александр II для осаждавших Барбастро. Флотилия была создана в результате коалиции пизанцев с генуэзцами и амальфитанцами, при этом пизанцы были в большинстве. В этой коалиции были и другие участники: например, Бенедикт, епископ Модены, занимал в ней весьма высокий пост. Был ли он представителем Папы? Как бы то ни было, именно его присутствие в окружении Матильды, маркграфини Тосканской, определило политический вес коалиции. Одно пизанское поэтическое сочинение, которое кажется достойным доверия в плане исторических сведений, говорит о неком знаке (signum) св. Петра на сумах (scarsellae) моряков: его можно истолковать как обычный знак на одежде (signa super vestes), означающий обет паломника и, кроме того, связать с папским отпущением грехов. Это не только совпадает со свидетельствами одной хроники из аббатства Монте-Кассино, согласно которой Папа — по обычаю, входившему в практику пап-реформаторов — передал флоту свое знамя (vexillum), но и на целое десятилетие опережает поступок, считающийся эпохальным, когда в Клермоне (городе, расположенном на пути в Компостелу) Папа Урбан II вручил знак креста (signum crucis) тем, кто откликнулся на его призыв помочь христианской Церкви на Востоке, которой угрожают неверные.