「如果他們打算今天開戰，就像男人一樣過來吧！」
——博希蒙德
匯聚在博斯普魯斯海峽東邊的十字軍呈現出了一種有趣的情況。中世紀的軍隊數量很難計算，不過當時可能有3萬名步兵、5 000名騎兵以及相當數量的非戰鬥人員。比起隱士彼得行動遲緩的平民部隊，他們顯得更有條理，不過在紮營的時候，帳篷依舊是散亂地簇擁在自己的貴族或是小領主周圍。只有拜占庭的隊伍秩序井然，這是阿歷克塞派出的分遣隊，由一位名為塔第吉歐斯的將軍率領，配有顧問，還隨軍攜帶了羅馬人多個世紀以來慣用的大型攻城車。
儘管籌備混亂，領導者各有心思，帝國軍和十字軍的利益也存在衝突，但大家對於接下來要做什麼仍有共識。如果想抵達耶路撒冷，就必須掃清道路通過小亞細亞，這意味著首先要攻破尼西亞。
尼西亞作為羅姆蘇丹國的首都，坐落於普羅戚提斯（Propontis） 附近的小湖旁，這裡是軍事要衝，守衛森嚴。從公元4世紀開始，它就是一座重要的城市，長達4英里（約合6千米）的城牆一直受到拜占庭人和之后土耳其人的精心維護。儘管它位於湖邊，在沒有海軍的情況下不可能真正包圍，但把它留給敵人也不可取。深入的十字軍很容易被切斷後路，陷入孤立無援的境地。
1097年夏初，十字軍拔營起程，向尼西亞前進。一路上，到處可以看到農民十字軍的可怕屍體，慘白的骸骨提醒著他們即將面對的風險和失敗的代價。因此，他們決定穩紮穩打，圍攻尼西亞。
與其說是十字軍蓄意而為，不如說他們紅運當頭，這個時機實在完美。土耳其蘇丹基利傑·阿爾斯蘭正忙著向東擴張領土，不願意半途而廢。他當然得知了有人東征的消息，但並未認真對待。隱士彼得之前的雜牌軍讓他覺得西方人根本算不上威脅，而間諜帶來的消息——彼得本人也參與了這次東征，則讓他更加確信了這一點。阿爾斯蘭把妻子、孩子和財產全部留在了尼西亞，他的自信可見一斑。
圍城的前幾天，情況似乎十分順利。儘管沒有一位最高領導人，但各親王與拜占庭友軍成立了指揮委員會，在沒有嚴重分歧的情況下達成了戰略共識，保持了一致的行動節奏。土耳其方仍然可以從水路獲取補給，他們向蘇丹瘋狂發信，請求他迅速回援。基利傑·阿爾斯蘭這時意識到自己判斷錯誤，匆忙揮師來救，但等他抵達的時候，軍隊士氣已經低落到了十分危險的程度。
1097年5月21日，蘇丹對敵人的低估讓他付出了慘痛的代價。在持續大半天的殘酷肉搏戰中，全副武裝的十字軍明顯佔據上風。戰至黃昏，基利傑·阿爾斯蘭開始向山區敗退。他放棄了救援尼西亞，讓妻子與孩子聽天由命。
十字軍高興地在土耳其人的營地里發現了繩索。這本是阿爾斯蘭計畫用來捆綁基督徒俘虜的，如今卻被用於土耳其人自己身上。他們把土耳其援軍士兵的頭顱砍下，投進尼西亞城裡，試圖進一步降低守軍的士氣。
然而，尼西亞的守軍展現出了比蘇丹更強的韌性。有一次，十字軍通過挖掘地道，成功摧毀了一座塔樓並放起大火，但土耳其人連夜將其修復。第二天早上十字軍醒來時，沮喪地發現自己的努力全部付之東流。親王們逐漸意識到他們需要幫助。尼西亞的食物和淡水儲備足夠支撐數月，只要他們的水路暢通，就能無限拖延下去。如果拜占庭海軍不封鎖尼西亞的港口，東征軍在可預見的未來難以前進一步。
收到親王的求援之後，阿歷克塞立刻派出了一支艦隊，斷絕了尼西亞與外界的聯繫。 收到消息的十字軍計畫在幾天後發動總攻。
土耳其守軍在湖中看到帝國正規軍的那一刻，就知道自己的抵抗已經沒有意義了。唯一的問題是如何避免城市的徹底毀滅，所以他們與拜占庭展開了秘密談判。在皇帝保證了城中居民的生命與財產安全，並承諾不讓一名十字軍士兵進城之後，尼西亞守軍投降了。當晚，通過湖邊的城門，帝國軍控制了城市，而守軍則從容撤離。
阿歷克塞就這樣收復了一座重要的城市，而且既保全了城市設施，又沒有得罪土耳其鄰居。不過無論此舉有多麼精明——這也是他要親王們宣誓效忠的確切原因——十字軍的領導者們已經體會到了拜占庭人的狡猾。第二天早上正是計畫開始總攻的時刻，但十字軍醒來卻困惑地發現帝國的鷹旗已然在城市上空飄揚。阿歷克塞的代表匆忙感謝十字軍的援助，慷慨地賞賜了親王，但普通士兵明顯有一種被欺騙的感覺。按照慣例，攻下城池後，士兵可以劫掠3天，這也是他們得勝的主要好處。不能劫掠也就意味著之前所有的圍攻都是白費力氣。
皇帝對待土耳其俘虜的手段又讓拜占庭與十字軍關係更加緊張。國家官員和富有的市民可以用錢贖身，重獲自由，而蘇丹的妻子則在君士坦丁堡享受了極高的待遇。阿歷克塞安排她住在皇宮，隨後又把她和孩子一起還給了阿爾斯蘭，沒有索要一分錢贖金。對拜占庭來說，這是個明智的做法。在東徵結束後，阿歷克塞還要與穆斯林鄰居相處，不能把關係搞得太僵。然而對十字軍來說，他們東征是為了打敗耶穌基督的敵人，這種做法只是坐實了希臘人的兩面三刀。
儘管有這些不快，但大家還是充滿了信心。第一次戰役結束了，十字軍取得了勝利。收復耶路撒冷彷彿指日可待。布洛瓦的斯蒂芬寫給妻子的信中洋溢著樂觀之情：「我們5周之內就能抵達耶路撒冷了，除非他們能在安條克擋住我們。」
從尼西亞到耶路撒冷的主路有兩條，一條沿著海岸線，另一條則直插烈日炙烤的內陸。阿歷克塞建議他們選擇靠海的那條，這樣海軍可以很容易為他們提供補給，但內陸的那條更近。尼西亞陷落一周後，十字軍出發了。他們沒有採納皇帝的建議，畢竟這段征程已經夠長了，最後的決定是把軍隊分成兩部分。
究竟應當由誰來率領十字軍？候選人逐漸縮減至兩位：博希蒙德和圖盧茲的雷蒙德。博希蒙德與拜占庭的嚮導關係很好，他擔心後勤補給出問題，因此提議分頭行動。雷蒙德對博希蒙德貪圖榮譽的行為早已不滿，此時樂得順水推舟。
兩支隊伍裝作不經意地錯開了一天的行程，想要劃清界限。而幸運女神再一次站在了十字軍這邊。失去了首都的基利傑·阿爾斯蘭吸取了教訓，這段時間一直在重整軍隊、簽訂協約，以便專心應對這次危機。他推測了十字軍可能採用的路線，並精心策划了一次埋伏，襲擊了博希蒙德。他認為所有的十字軍都已經落入了他的陷阱。
博希蒙德的迅速反應阻止了一場徹底的災難。他讓騎士下馬，圍成一個大圈，保護那些非戰鬥人員，並派信使前去尋找雷蒙德的隊伍。他們只知道雷蒙德大概的方位，不過只花了5個小時就找到了對方。與此同時，土耳其人沒有取得什麼戰果。儘管他們的數量遠超十字軍，但重裝騎士的防線很難突破。阿爾斯蘭的軍隊大部分都是輕裝的弓箭手，移動迅速。除了少數人冒失突進了一次之外，博希蒙德的軍隊成功抵制了出擊的誘惑，從而保持了陣形，避免了自己的毀滅。
雷蒙德軍的到來讓阿爾斯蘭大吃一驚。形勢完全逆轉，土耳其人成了被包圍的一方，被十字軍里外夾擊。在接下來的混戰中，大部分土耳其人都被殲滅，剩下的一些則拋下輜重和財產逃走了。
這次勝利是雷蒙德和博希蒙德共同的功勞，它摧垮了塞爾柱土耳其人的戰意。阿爾斯蘭認為十字軍太強大了，無法阻擋，於是帶走了沿途鄉間的所有供給，並躲得遠遠的。在休息幾天之後，十字軍再次出發，他們計畫穿過托羅斯山脈（Taurus Mountains）附近的荒涼地帶向東南前進。
接下來4個月里，在荒無人煙的環境中行軍的東征者逐漸意識到，盛夏時分穿越熾熱的安納托利亞高原是一件愚蠢的事情。土耳其人帶走了幾乎所有食物，路上的水源也少得可憐。更糟的是，儘管酷熱難當，但十字軍不得不身穿盔甲，以免遭到埋伏。在馱畜開始死亡後，隨軍的羊、豬甚至狗都被暫時徵用。許多騎士不得不走路前進，讓馬去背負物資。一些受傷的士兵也只能留下休養。
唯一保持士氣，讓十字軍堅信自己受到了上帝保佑的事情，就是他們不斷的勝利。抵達托羅斯山脈關口時，一批不屬於基利傑·阿爾斯蘭的土耳其人想要阻止十字軍。博希蒙德幾乎單槍匹馬就搞定了對手，他直接沖向對方的埃米爾，並在決鬥中輕鬆獲勝，令土耳其人為之膽寒。他們四散逃竄，之後再沒有試圖阻擋過東征。
這次決鬥最大的獲益者是博希蒙德，他在戰爭中的聲望開始超越雷蒙德。與土耳其人交鋒的耀眼表現在當晚被添油加醋傳遍了整個十字軍，而偶然出現的彗星又被許多人解讀為博希蒙德崛起的徵兆。博希蒙德覺得這是一個趁熱打鐵的好時機，就派外甥坦克雷德和一些小貴族離開大部隊，去解放附近的幾座城市。隨後，他又把這些城市逐次交還給阿歷克塞，以展現他的誠意，並暗示皇帝他還是有資