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