В первые годы царствования внимание нового императора было обращено на норманнов и печенегов. Положение Византии в Малой Азии выглядело довольно устойчивым: там было много населенных пунктов, которые за десятилетие после сражения при Манцикерте оказывали серьезное сопротивление туркам и продолжали держаться и после восшествия Алексея I на престол. Во многих случаях причиной успешного сопротивления были эффективные действия местных властей, а не помощь Константинополя. Например, обороной области вокруг Трапезунда на северном побережье Малой Азии руководил Феодор Гавра, отпрыск одного из самых могущественных семейств города. Ярость, с которой Гавра защищал земли вокруг Трапезунда, была такова, что турки с восхищением упоминали ее спустя столетие в лирической поэме о завоевании Малой Азии. Обширным районом вокруг города Амасья в 1070-х годах в высшей степени эффективно управлял норманн Руссель де Байоль, который сначала находился на императорской службе, но затем провозгласил независимость от Византии, так был выведен из себя отсутствием поддержки от правительства. Этот чужеземец пользовался огромной популярностью у местного населения, которое буквально носило его на руках в благодарность за защиту, которую он обеспечивал.

Византийские полководцы удерживали населенные пункты далеко на восточных окраинах Анатолии и даже на Кавказе. Трое сыновей Мандала, по словам одного закавказского летописца, «римские магнаты», в 1080–1081 годах занимали опорные пункты в районе Кесарии, вероятно действуя от имени империи, а не с выгодой для себя.