11世紀80年代末，除了仍由阿布勒-卡西姆掌權的尼西亞外，拜占庭保持了對東部諸省許多重要地區的控制，尤其是關鍵的沿海地區：肥沃的各個河谷地區以及愛琴海諸島，也就是對帝國的貿易和交通網路異常關鍵的戰略敏感地帶。這一時期，這些地方大都在拜占庭的控制下繁榮發展著，證據是：1088年和1089年萊羅斯島（Leros）和帕特摩斯島（Patmos）等諸島上的僧侶們多次接待了皇帝阿萊克修斯的母親。他們當時正在籌劃一項宏大的建造計畫，希望得到可貴的免稅權。
但局勢很快發生了急劇的轉變。我們之前已經看到，1090年時，佩切涅格人對西部諸省的侵擾陡然加重。前些年還只是零星的游擊騷擾，這時卻整個部落都已移民到色雷斯腹地。這種壓力給東部的突厥軍事豪強們提供了絕佳的時機，起而反抗拜占庭帝國。阿布勒-卡西姆也真的這樣做了。大約在1090年年中，他開始著手準備進攻尼科米底亞。這座城鎮坐落在尼西亞以北，離君士坦丁堡只有50英里。
阿萊克修斯一世竭盡全力想要保住這座城鎮。佛蘭德斯（Flanders）伯爵羅貝爾（Robert）在1089年底結束耶路撒冷朝聖之旅的返鄉途中與阿萊克修斯一世見了一面，他答應派出500名佛蘭德斯騎士來為拜占庭皇帝效勞。這批人馬本來是打算用於對抗佩切涅格人的。 但當他們在次年年中來到拜占庭境內時，卻很快被運送到博斯普魯斯海峽對岸，以增援尼科米底亞。事實證明，他們的到來具有立竿見影的效果。但1091年春，騎士們又被召回來轉去拉維尼歐對抗佩切涅格人。 尼科米底亞是小亞細亞最古老也是最著名的城市之一，這座曾在公元3世紀一度成為羅馬帝國東部都城的城市，隨即落入阿布勒-卡西姆之手。 對拜占庭而言，失去尼科米底亞是一場災難，人們開始質疑帝國是否能長久保有東部所有省份。
還有其他勢力也正虎視眈眈地想要趁火打劫，這讓人們進一步加深了對拜占庭在小亞細亞前景的質疑。一位頗具個人魅力的突厥軍事領主達尼什蒙德（Danishmend）從小亞細亞東部發動了令人生畏的攻襲，一直深入到卡帕多契亞，目標指向塞巴斯蒂亞（Sebasteia）和凱撒利亞等主要城鎮。 還有察卡（Çaka），他是個野心勃勃的突厥人，以小亞細亞西海岸的士麥那為大本營，確立了自己的勢力範圍。他付錢讓當地的造船商為自己建造了一支艦隊，襲擊了自己新基地周邊的一系列目標，包括愛琴海諸島。 其他暫且不談，這些襲擊的後果與丟掉尼科米底亞一樣糟。察卡的艦隊具有遠程攻擊的能力，可以騷擾沿海城鎮和島嶼的船運，而船運對君士坦丁堡來說是至關重要的。由於佩切涅格人的威脅，此時首都的供給已經備感壓力，海運受到的干擾更是加重了供給短缺、通貨膨脹和社會動蕩。更嚴重的是，1090年—1091年，人們經歷了記憶中最為嚴酷的冬天，紛飛的大雪讓許多人只能被困家中。
一首大約寫作於這個時期的詩作，描繪了一位來自小亞細亞某個省份的女性實在飢餓難耐，不得不去吃蛇肉的情景：「你整吞或分食過蛇肉嗎？你是把它們的頭和尾巴切掉，還是所有部分都吃掉？你是怎麼做到吃了這些充滿毒液的肉卻沒有即刻喪命的呢？」嚴冬、大饑荒和野蠻人災禍共同帶來了如此慘痛的後果。
對抗察卡的舉措實在是一團糟。一位當地的總督毫無抵抗就棄城逃走，而皇帝派來保衛小亞細亞西部沿海地區的援兵則是匆匆拼湊起來的，最後毫無意外地大敗而歸。拜占庭的艦隊不僅遭遇慘敗，而且有好幾艘艦船被察卡俘虜。這些艦船大大便利了他在別處的斬獲。
察卡的艦隊逐步成了氣候，這也給拜占庭帶來了另一層隱憂。君士坦丁堡在陸地上有堅不可摧的城牆、壕溝和重裝哨塔護衛，但拜占庭人一直對未來可能的海上攻擊憂心忡忡。雖然有一根巨大的海上防衛鏈橫亘在通往金角灣的入口處，讓人多少有點兒寬慰，可它實際上往往不起作用。來自海上的進攻，哪怕只是一小股游擊勢力，也會讓城中居民惶恐不安甚至歇斯底里。這樣的情況在公元9世紀和10世紀都發生過，當時維京和羅斯的游擊武裝突襲了君士坦丁堡的近郊地區，結果造成了普遍的恐慌。至於察卡，人們擔心，這個突厥人或許會與佩切涅格人達成合作，攜手對都城發動進攻。1091年春，有這樣的流言四處散播：佩切涅格游牧民族與察卡之間有所往來，而察卡將協助他們對抗拜占庭帝國。
都城內氣氛壓抑，人心浮動。1091年春，當著皇帝阿萊克修斯一世及其隨從們的面，安條克牧首奧克斯特的約翰（John the Oxite）七世回顧了帝國所處的困境，言語中頗多怨言。也不過就在三年前，奧赫里德的提奧菲拉克特的致辭還是積極樂觀的，如今約翰的態度卻截然相反了。牧首說，開俄斯（Khios）島和米蒂利尼（Mitylene）已經失陷，愛琴海諸島已經全部淪陷，而小亞細亞則完全陷入混亂之中，東部已經片土不存。 與此同時，佩切涅格人已經兵臨君士坦丁堡城下，而事實證明，阿萊克修斯的應對方式根本就不奏效。 在思索為何威脅會變得如此嚴重時，約翰得出了一個直接而尖銳的結論：上帝已經不再守護拜占庭。軍事上鮮有勝績，嚴峻的困境卻曠日持久，這一切都乃皇帝之過，牧首這樣宣稱。在登上帝位之前，阿萊克修斯一直是一名優秀的將領，但自此之後他卻吃了一場又一場的敗仗。1081年，他奪取帝位，觸怒了上帝，上帝如今借異教徒之手來懲罰拜占庭。想要改變形勢，亟須皇帝悔悟贖罪。 這種末世論式的裁決強有力地表明，11世紀90年代初困擾著拜占庭帝國的種種問題是多麼嚴重。
生活在拜占庭帝國境內的西方人以驚恐的心情觀察著小亞細亞局勢的迅速惡化。「突厥人與多方結盟，入侵本應屬君士坦丁堡的帝國領土，」一位來自法國中部的見證者寫道，「他們洗劫了各地的城市、城堡及其殖民地，教堂被夷為平地。被他們抓住的教士和僧侶們，有些遭屠戮，其他人則懷著無法言表的罪惡感棄主而去，拜服於強權。而修女們（哦，真是慘啊）則在他們的獸慾下遭難。如同飢餓的狼群，他們無情地捕獵，而上帝在公正裁決之後，把某些基督徒交到他們手上聽憑其處置。」
小亞細亞局勢已經失控，這類令人沮喪的消息很快傳遍了整個歐洲。比如，法國各地都聽說了各種有關突厥人在那裡殺人放火、奸淫擄掠的故事，而僧侶們則在編年史中記述了大量充滿暴力血腥的場景，如挖人內臟、斬首等等。 這類消息是由11世紀90年代初住在或到訪過君士坦丁堡的西方人傳播開來的，比如某個來自坎特伯雷但定居在這座都城的僧侶，或是對君士坦丁堡的壯觀景象萌生敬意、讚歎地描述所見所聞，並記錄下自己與城中居民交談所得的某位旅人。
阿萊克修斯本人也傳播了拜占庭人在突厥人手中遭受暴行的消息。他在送給佛蘭德斯伯爵羅貝爾的一封信中，就以令人沮喪的口吻描述了1090—1091年間小亞細亞的局勢。 這份通信一直以來都被視為偽造的，數代學者都認為其內容並不可信，理由是拜占庭1081年就已經失去了東部諸行省，他們判斷自那時起到第一次十字軍東征前期，東部行省的局勢並不可能發生重大變化。於是，他們普遍認為，信中所聲稱的拜占庭人與突厥人力量對比發生的大逆轉，根本是毫無事實依據的。學者們振振有詞地認定，這封信是偽造的，因為在12世紀初，當阿萊克修斯與第一次十字軍東征的一些主要人物關係無可挽回地破裂之後，這封信曾被用來集聚起各方反對拜占庭的力量。
不過，另一點人們卻相當肯定，即考慮到兩人之間關係的密切，11世紀90年代初阿萊克修斯的確有可能寫了一封信給佛蘭德斯伯爵。既然是這樣，那麼，這封流傳下來的信確實是源自君士坦丁堡的一份原始文件——但經過了再詮釋和不必要的添油加醋。 確實，這封信採用的辭令和書寫語言毫無疑問是拉丁式的，而其中體現的外交和政治思想也顯然是西方式而不是拜占庭式的。
雖然如此，這也並不意味著這份文本是偽造的。我們之前已經看到，11世紀末，君士坦丁堡住著許多西方人，其中有些人與皇帝的關係還很親近。那麼，信中的語氣和觀點很可能表明它出自某位客居帝都的人之手，這種可能性和它出自某位生活在第一次十字軍東征之後的作者之手一樣大。如果這麼看的話，這封信最讓人震驚的地方或許在於，它所說的一切與根據當時的其他文獻構築起來的小亞細亞新圖景高度吻合。這封給佛蘭德斯的羅貝爾的信也描述了11世紀90年代教堂紛紛遭褻瀆的景象。這與我們從其他文獻中了解到的一樣：「聖所遭褻瀆，遭損毀，種種情狀難以勝數，而更糟的預期還在等著它們。此情此景，誰不憂傷？聽聞此事，誰無同感？誰不會聞之駭然？誰不會禁不住祈禱求助？」 信中還描述了突厥人之兇狠殘暴，這也同樣印證了當時