Отправившись из Ионии на юг, Александр тут же принялся завоевывать средиземноморское побережье Малой Азии. Кария подчинилась ему с помощью престарелой принцессы Ады, сестры покойного Мавсала, которого другой ее брат, Пиксадар, отстранил от власти: молодой царь оказал ей почет и уважение и даже позволил, чтобы она признала его своим сыном. Он впервые применил оригинальную политику личных союзов с местными правителями, которая широко использовалась впоследствии. Однако крупный прибрежный полис Галикарнас, главный порт Карии, куда отступил Мемнон, поддерживаемый персидским флотом, пока еще невредимым и мощным, отбил первые атаки: пришлось брать город длительной осадой, а Мемнон бежал морем. Александр, несмотря на начавшийся неблагоприятный сезон, продолжил путь по прибрежным регионам — в Ликию и Памфилию, которые покорил одну за другой. Затем он взял северное направление на Писидию и Фригию, где в самом сердце Анатолии, в Гордионе, древней столице царя Мидаса, соединился с подразделением, отправленным туда из Карии под командованием Пармениона. Именно там зимой 334–333 годов он увидел в храме колесницу основателя фригийской династии Гордия: по древнему преданию, азиатская империя будет принадлежать тому, кто сумеет развязать сложный узел, затянутый на дышле колесницы. Александр, согласно некоторым из его историографов (которым современные критики в этом вопросе не склонны доверять), разрубил ударом меча знаменитый гордиев узел. Правдивый или вымышленный, этот случай замечательно демонстрирует характер завоевателя, желающего поразить воображение толпы, прислушивающегося к предсказаниям оракулов и ненамеренного медлить, поэтому эта история имеет вполне заслуженную славу.
Тем временем Дарий и его военачальники производили реорганизацию своей армии, которая не обошлась без трагических событий. Мемнон, со своим флотом занявший Хиос и высадившийся на Лесбосе, умер на этом острове, когда осаждал Митилену: так Великий царь лишился лучшего из своих стратегов. Персидский флот после этого сыграл весьма незначительную роль, совершив несколько рейдов в Эгейском море. Дарий собирал свои силы в Сирии, куда должны были прибыть греческие наемники Мемнона. Афинянин Харидем советовал ему опереться на них, чтобы выступить против македонской армии с сильным войском, закаленным и сплоченным. Но ревность персидской знати к этому греку заставила отказаться от этой, возможно спасительной, идеи, а Харидем, который не захотел подчиниться по доброй воле, был отправлен разгневанным Великим царем к палачу. В итоге атаки Александра ждала многочисленная, но разношерстная армия: к боевому корпусу, сформированному из наемников, были присоединены небольшие отряды азиатов и иранская конница.
Александр, оставив побережье Черного моря, поручил одному из лучших своих военачальников, Антигону, контролировать Фригию и охранять от любого посягательства западную границу своих анатолийских завоеваний, проходящую по реке Галис. Антигон до самого конца царствования Александра проявит себя достойным такого доверия. Сняв с себя эту заботу, царь направился в Сирию, ясно показав тем самым, что он не намерен ограничиться завоеванием Малой Азии. Болезнь ненадолго задержала Александра в Киликии, в Тарсе, где его лечил врач Филипп из Акарнании. Однажды, принимая из рук врача лекарство, Александр получил письмо от Пармениона, предупреждавшего, что Филипп был подкуплен шпионами Дария, чтобы отравить Александра. Бесстрашный царь протянул письмо врачу и выпил чашу со снадобьем: доверие, которое он питал к своим друзьям, не могли поколебать ложные доносы. Этот жест демонстрирует ту склонность к риску, которой он любил поражать свое окружение.