Сопротивление македонской армии оказали лишь Милет и карийский центр Галикарнас, где стояли сильные греческие наемные гарнизоны. При взятии Милета Александру помог грекомакедонский флот. Опередив персидскую эскадру на несколько дней, командующий этим флотом Никанор запер бухту Милета. Сам же царь атаковал город с суши, его войска вошли в пределы крепости через проломы, сделанные метательными машинами. Во взятом городе Македонский властитель долго рассматривал статуи, посвященные выходцам из Милета, которые выигрывали Олимпийские игры, после чего с издевкой спросил: «А где были эти молодцы, когда персы брали ваш город?» Исследователи усматривают здесь особый подтекст, ведь сам Александр не принимал участия в Олимпиадах. Взятие Милета, у которого было еще восемьдесят колоний, имело, конечно, большой резонанс во всем эллинском мире.
В Галикарнасе персам, наоборот, удалось использовать свой флот. Помешать взятию города он не смог, но имевшиеся здесь силы вывез, когда Галикарнас был занят македонцами. Наступая на этот город в области Кария, Александр продемонстрировал и способности дипломата. Дабы заручиться поддержкой части местного населения, он поддержал притязания на трон царицы Ады, свергнутой с престола в 340 году до н. э.
После взятия Милет Александр распустил свой флот, что было довольно-таки неожиданно. Этому можно найти несколько объяснений. Царь понимал, что его корабли все равно не могут соперничать на море с кораблями персов, а потому следует захватить базы флота, что само по себе заставит капитанов перейти на сторону новых хозяев. Учитывая ход дальнейших событий, такая версия выглядит очень правдоподобно. Александром могло также двигать желание, чтобы его воины и думать не смели о возвращении до окончательной победы над противником[11]. Наконец, флот мог понадобиться в Греции, чтобы препятствовать вхождению в местные гавани вражеских судов.
Зимой 334/333 года до н. э. македонская армия заняла, фактически не вступая в бой, Ликию и Памфилию, затем поднялась на север и покорила Великую Фригию. Именно здесь Александр якобы разрубил сложный узел, завязанный когда-то на своей колеснице царем Гордием, предсказавшим, что тому, кто справится с узлом, предстоит править Азией. Это далеко не единственная история из своеобразной агиографии выдающегося правителя. Вероятно, придворные историки сознательно еще при жизни царя создавали образ человека, который действует в союзе с богами, обосновывали его притязания многочисленными чудесами и знамениями. В одной реке была якобы найдена табличка с древними письменами, которые сообщали, что Персидское царство падет под ударами эллинов. В другом месте упавшая сама по себе в пыль статуя сатрапа подтверждала неотвратимость успеха для македонян. Подобно водам Красного моря, волны сами отступили от берега, когда Александр совершал рискованнейший переход по узкому горному карнизу, нависавшему над морем в районе города Перга.
Персы тем временем не сидели сложа руки. Верховное командование было поручено Мемнону. Весной 333 года до н. э. флот Мемнона безраздельно владел Эгейским морем. Были захвачены Хиос и большинство городов на острове Лесбос. Корабли родосца доходили до самого побережья Македонии. Ходили слухи, что он готов захватить остров Эвбея, с которого можно было спокойно переправляться на Балканский полуостров. Персидское золото привлекало все новых наемников. В пользу Персии начали склоняться жители Кикладских островов и материка, в переговоры с персами вступила Спарта, послали к персидскому царю своих гонцов и Афины. Когда же Македония несколько необдуманно воспрепятствовала греческому судоходству в Геллеспонте, «нейтральные» Афины пригрозили послать туда сто кораблей из своего могучего флота. Этого оказалось достаточно, чтобы пролив снова был освобожден. Спартанский царь в результате все же попытался поднять против Македонии общегреческий мятеж. Однако сработал стратегический резерв: Антипатр подавил все мятежи, не дав высадиться в Греции персидскому десанту. Вскоре, в связи с успешными действиями Александра в Финикии и усилившегося греко-македонского флота на островах, персидский флот прекратил свое существование. Спарта же вынуждена была присоединиться к Коринфскому союзу незадолго до битвы при Гавгамелах.
Большой удачей для македонского правителя стала смерть Мемнона в мае 333 г. до н. э. Так Александр избавился от одного из опаснейших внешних врагов. Но царя уже беспокоила мысль и о внутренних противниках. Поэтому он охотно принял за чистую монету оговор, которому подвергся оставшийся в живых Александр Линкестид. Последний был срочно вызван к царю, но пока не казнен, а лишь закован в кандалы и оставлен при царском лагере.