追殺比修斯
在處理內部的反對派的同時，亞曆山大並沒有放鬆對外部敵人的鬥爭。大流士死後，比修斯就成了他的主要對手。比修斯已自封為波斯國王，他還擁有不可忽視的軍事力量，足可與亞曆山大一戰。但亞曆山大在追擊比修斯之前，和他曆來的作法一樣，先做了些必要的準備工作，鞏固後方，去掉隱患。他首先率兵進攻裏海之濱的赫卡尼亞，並委任帕西亞人阿明那匹斯為帕西亞總督，這人在埃及和馬紮西斯一起投降了亞曆山大。委任近衛軍將領特萊波利馬斯為帕西亞和赫卡尼亞的軍事總監。然後他分兵三路，進入艾爾布爾茲山地，征服塔普裏安與馬爾地安等部落，搜索隱藏在山地的大流士餘部和希臘雇傭軍。一路由他自己率領，沿著一條崎嶇難行的近路前進，這是軍隊的主力，是一支精兵隊伍；第二路直接去攻擊塔普裏安人；第三路護送輜重、行李和車輛，沿大路前進。亞曆山大率兵以極快的速度越過山口，在一條小河邊宿營，這時，被追得無路可逃的波斯高級將領、騎兵大將那巴讚斯、帕西亞和赫卡尼亞總督福拉塔弗尼斯等都前來投降。在這裏停了幾天，亞曆山大又率兵向赫卡尼亞內地的紮德拉卡塔城進發。在紮德拉卡塔，亞曆山大和另外兩路人馬會合了。亞曆山大在這裏接受了與比修斯分道揚鑣的波斯帝國首相拉巴爾查尼斯、重臣阿爾塔巴紮斯和他的三個兒子的歸順。跟他們一起來的還有1500名希臘雇傭軍的代表和希臘各城邦派駐波斯帝國的使臣。亞曆山大對來歸順的波斯人很寬容，給他們榮譽地位，稱讚他們對大流士的忠心；而對希臘人卻很嚴厲，他拒絕和他們談任何條件，因為他們跟著外國人打希臘人，犯了嚴重的罪行，隻有集體投降，由他來決定怎樣處理他們。如果他們不願意這樣做，他們可以自己決定采取什麼方法來保護他們自己的安全。雇傭軍的代表當即表示，全體雇傭兵都同意投降，因營地較遠，請亞曆山大派專人前去把他們帶來。亞曆山大同意這樣辦，派了兩個將領去接收希臘雇傭軍。亞曆山大在營地接見了他們和希臘各城邦派駐波斯的使臣。對希臘雇傭軍，凡是在希臘各城邦跟馬其頓議和並結盟之前就在波斯部隊服役的，亞曆山大放了他們，恢複他們的自由；其餘的則都編入馬其頓部隊，繼續服役。對於各國使臣，亞曆山大也根據不同情況區別對待，斯巴達和雅典的使臣被監禁起來，因為雅典使臣明知違犯聯盟章程卻仍能來波斯，而斯巴達的使臣則因為沒有在斯巴達加入希臘聯盟後卸任。非同盟國的使臣都被釋放了，因為這些國家派使臣到波斯並沒有什麼不對。亞曆山大在這裏顯示了他政治家的風度。
在接收希臘雇傭軍時，亞曆山大還率部進攻馬爾地安人。馬爾地安人所居地區，交通閉塞，與外界很少往來，居民生活十分貧困，但卻勇猛好戰。他們有很長時間沒有受到外族的入侵了，因此沒有做任何抵抗入侵者的準備。當亞曆山大率兵攻來時，他們非常吃驚，來不及作任何抵抗，但有一大批人逃到山裏去了。他們認為，山高路陡，亞曆山大不會到這樣遠的山裏來。而亞曆山大偏又追來了，他們無處可逃，隻好派代表出來投降，獻出領土。亞曆山大委任波斯人、原塔普裏安總督奧托夫拉達提斯為馬爾地安和塔普裏安的總督。
然後，亞曆山大率部去赫卡尼亞的最大城市（也是王宮所在地）紮德拉卡塔，他在這裏停了15天，向神獻祭和舉行體育競賽。接著率軍進入阿瑞亞境內，到達蘇西亞城時，阿瑞亞總督薩提巴讚斯前來迎接，亞曆山大讓他留任阿瑞亞總督。並派一名近衛兵將領率40名馬上標槍手在沿路站崗，以免後續部隊通過時騷擾阿瑞亞人。亞曆山大為在當地居民中樹立一個好形象，不能說做得不好，但效果卻不像他所期望的那麼好。
這時有波斯人來向亞曆山大報告說，比修斯已不再叫比修斯了，而稱阿太薛西斯，他按國王的樣子戴帽子，穿皇家的錦袍，儼然以亞洲之王自居。亞曆山大感到消滅比修斯的勢力，活捉比修斯，已刻不容緩了。他立即率領經過整編的全部軍隊向巴克特利亞前進，但在進軍途中卻接到一個使他不得不改變行軍路線的消息。不久前才投降的阿瑞亞總督薩提巴讚斯，出於民族情緒，在比修斯的支持下，趁亞曆山大進軍巴克特利亞之機，在後方發動了叛亂，殺死了留駐當地站崗的馬其頓馬上標槍手和帶隊將領。他把阿瑞亞人都武裝起來，進入阿瑞亞王宮所在地阿塔考那城，並決定帶領部隊去會合比修斯，準備和比修斯一起伺機攻打馬其頓部隊。
亞曆山大這時已進軍到巴克特利亞邊境附近的馬迦斯河旁，但仍然決定回師平定叛亂。除留下一部分部隊，由克拉特拉斯率領、在馬迦斯河邊待命外，亞曆山大親自率領近衛騎兵、馬上標槍手、弓箭手、艾吉裏亞部隊和兩個步兵旅返回阿瑞亞，火速追趕薩提巴讚斯，兩天後就到達阿塔考那城。薩提巴讚斯沒想到亞曆山大這麼快返回來攻擊他，沒有抵抗，就急忙帶著少數阿瑞亞騎兵逃跑了。他部下的大部分士兵則一哄而散。但亞曆山大並沒因叛亂者逃散而就此罷休，他又一次顯示了他嚴酷的一麵。他迅速地進行搜捕，把那些離開村莊參與叛亂的人從各處搜出來，一一就地殺戮，其餘的沒參加叛亂的村民則都貶為奴隸。他要用這樣的血腥行動告誡所有的被征服的人們，叛亂者會受到嚴厲的懲罰。他廢棄了阿瑞亞的舊都阿塔考那，而在它的旁邊另建了一座新城，新城被命名為“阿瑞亞的亞曆山大”，同時委任波斯人阿薩米斯為阿瑞亞的新總督。這時，留在馬迦斯河畔的克拉特拉斯率領的部隊也到阿瑞亞和亞曆山大會合，於是，亞曆山大率領全軍向南邊的紮蘭迦亞地區前進，當時占據這一地區的是巴散提斯，這個人曾在大流士逃跑時參與謀害他，見亞曆山大大軍快來了，就逃跑到印度河這邊的印度人地區。但印度人卻把他抓住送交亞曆山大，亞曆山大就因他參與謀殺大流士而把他處決了。接著，亞曆山大又到西邊的阿拉科提亞（阿富汗）地區捉拿參與叛亂的波斯總督阿薩提斯，並就地處決。然後在弗裏達建立了一座取名為“亞曆山大希望城”的新城。
這時軍隊中出現嚴重的不滿和厭戰情緒，因為從波斯波利斯開始，戰爭成了一場對一個亡命君主和一個弑君者的追逐。對於亞曆山大的將士來說，戰爭已毫無吸引力。為平息將士的不滿，亞曆山大以叛國罪處死了功高權重的帕米尼歐父子，並對部隊的核心部分的指揮官進行了調整。原由菲洛塔斯擔任的騎兵司令一職，改由赫斐斯申和克雷圖斯兩人擔任，各指揮一個旅，以免權力過分集中。托勒密被任命為皇家衛隊長。而帕米尼歐副統帥一職也早已由克拉特拉斯擔任了。
隨後亞曆山大率軍進入阿瑞阿斯皮亞人居住的地區，因為這一地區的人民曾為居魯士出過力，亞曆山大對他們有好感，便允許他們自治。
接著亞曆山大就繼續向巴克特利亞前進，追擊比修斯。沿途征服了德蘭吉亞人、迦德羅西亞人和阿拉科提亞人，委派了新的總督。公元前329年冬季，他率部到達塔爾拉克河畔印度人居住的地區。他一路行來，克服了很大的困難，饑餓、疲勞、積雪、寒風使部隊吃了不少苦頭。將士們有時隻能靠獵取野生動物為食，不少人病倒了，還有許多戰馬凍死在雪地上。
就在亞曆山大向巴克特利亞艱苦挺進途中，又傳來薩提巴讚斯再次在阿瑞亞進行叛亂的消息。薩提巴讚斯從比修斯處得到2000騎兵後，又侵入阿瑞亞，發動當地人跟著他造反。亞曆山大隻好又分出一部分兵力來對付薩提巴讚斯。這次他沒有親自回師鎮壓，而是派波斯人阿塔巴紮斯和兩位騎兵將領率兵去征討，同時令帕西亞總督前往支援，對薩提巴讚斯形成東西夾攻之勢。一開始，薩提巴讚斯的部隊進行了頑強的抵抗，和馬其頓的騎兵部隊展開了一場激戰，但隨著薩提巴讚斯臉上中槍而死，他的部隊瓦解了，抱頭鼠竄了。