Скрывшись за стенами Константинополя, император начал искать помощи других латинских союзников, в частности германского императора Генриха IV, который, насколько Алексей знал, враждовал с итальянскими норманнами. Посланники византийского императора предложили Генриху IV 144 000 золотых номисм за то, чтобы тот вторгся на земли Гвискара в Италии. Генрих деньги взял, но союзником оказался ненадежным. Он не снаряжал поход в Италию до самого 1084 года, но и тогда его целью оказался Рим, а не норманны. Однако эта угроза заставила Роберта Гвискара пересечь Адриатику в обратном направлении. Воевать с Алексеем он оставил своего сына Боэмунда.
Более значимую роль в борьбе с норманнским вторжением сыграл другой западный союзник. Расположенная в верхней части Адриатики морская республика Венеция могла легко использовать свой флот, чтобы помешать переправке людей и грузов в расположение норманнов на Балканах. Кроме того, в ее интересах было прийти на помощь византийцам, поскольку в планы венецианцев не входило, чтобы оба побережья Адриатики находились под властью одного государства. Нападения венецианцев на норманнский флот, везущий припасы и подкрепление, несомненно сдерживали вторжение, которое перед лицом упорного сопротивления постепенно ослабевало. В 1085 году норманны отступили.
С помощью латинян удалось расправиться и со старым врагом, печенегами, которые все еще не были покорены и бесчинствовали на Балканах. В суровую зиму 1090–1091 годов они дошли до предместий Константинополя и на протяжении многих недель никто не осмеливался выходить за пределы городских стен в занесенные снегом поля. С наступлением весны Алексей выступил против печенегов. В составе его войска были 500 рыцарей, которых направил к нему граф Фландрский, другие латинские наемники, прибывшие из Рима, а также представители еще одного степного племени, половцы. 29 апреля в битве при Левунионе во Фракии эта смешанная армия нанесла сокрушительное поражение печенегам, уничтожив все их войско численностью в несколько тысяч. На следующий день после боя победителям пришлось спешно покинуть это место из-за зловония, исходившего от такого количества трупов. Освобожденные жители Константинополя, ликуя, пели на улицах: «Всего один день, и печенеги никогда не увидят месяц май!» С учетом того, что помощь латинян сыграла решающую роль в восхождении Алексея на престол и одержанных им победах над норманнами и печенегами, неудивительно, что он продолжал привлекать все больше наемников и союзников с Запада. В отличие от своих предшественников, которые довольствовались союзами с теми, кто сам стремился к ним, Алексей решил закинуть сети дальше и отправил своих посланников в далекие края Западной Европы, к королю Англии, графу Фландрии и даже к Папе Римскому. Это было как никогда актуально, поскольку теперь, когда с Запада империи ничего не грозило, Алексей и его советники решили вернуть византийские территории на Востоке и изгнать турок с земель, которые те заняли после Манцикерта. При этом Алексей, похоже, несколько изменил традиционный способ вербовки союзников и наемников. Как всегда, им сулили много золота, но добавились и новые стимулы. Упор делался на том, что византийцы и латиняне были христианами, а турки в Малой Азии – нет. Таким образом, для христианского императора борьба против «неверных» становилась праведным делом, за которым должно было последовать не только материальное, но и духовное вознаграждение. Возможно даже, посланники Алексея упоминали Иерусалим, который, хотя и лежал далеко за пределами Византии, прочно занимал воображение латинян, как место на земле, расположенное ближе всего к небесам. Конечно, это лишь предположение, поскольку записей того, что говорили византийские посланники, нет. Но если они делали это по поручению императора, то Алексей отчасти несет ответственность за то, что произошло дальше.