Мемнон, завладев Косом и Хиосом, сосредоточился на острове Лесбос, на котором, как уже упоминалось, ему сопротивлялась только Митилена. По сообщению Арриана, он обнес город двойным палисадом, отрезав от моря, возвел пять укреплений и «оказался с суши хозяином положения». Флот Мемнона караулил входы в гавань и подступы к грузовым причалам. Казалось, еще немного — и Митилена падет. Но в мае 333 года Мемнон неожиданно умер от болезни. С его смертью ситуация резко изменилась по словам Диодора, «смерть Мемнона погубила все дело Дария».
Александр не зря считал Мемнона самым опасным своим противником. Грек по рождению и образу мыслей, стратег не по должности, а по призванию, Мемнон сумел организовать реальное сопротивление македонскому натиску. На суше он, после поражения при Гранике, с определенным успехом использовал тактику партизанской войны, а на море, опираясь на многочисленный и боеспособный персидский флот, вел наступательные операции и угрожал глубокому тылу македонян. Его смерть развязала Александру руки: царь полагал, что Дарию некем заменить Мемнона, — и полагал совершенно справедливо. Безусловно, в нем говорило эллинское презрение к варварам, которым «не хватает мужества» и которые потому «живут в подчинении и рабском состоянии». Однако, как показали дальнейшие события, Александр был недалек от истины.
На персидском военном совете в Вавилоне решили передать командование флотом Фарнабазу, племяннику Мемнона. Воодушевленный этим решением, Фарнабаз принудил Митилену к сдаче на условиях расторжения всех договоров с македонским царем и возвращения изгнанников. После этого персы двинулись к острову Тенедос, который расположен в 12 милях от Геллеспонта; тот, кто владел Тенедосом, контролировал торговые коммуникации. Жители Тенедоса покорились Фарнабазу, поскольку на стороне последнего было значительное превосходство в силе. Гегелох со своими кораблями благоразумно отступил.
А вскоре персы потерпели первое поражение на море. Разведывательная эскадра в составе 10 триер под командой перса Датама была разбита у Кикладских островов кораблями Протея, посланца Антипатра: восемь триер пустили ко дну, ускользнуть удалось лишь двум. Некоторое время спустя Гегелох освободил Тенедос и другие острова, причем не встретил сколько-нибудь серьезного сопротивления (почему — об этом чуть ниже).
Что касается сухопутного командования, тут Дарий пошел поначалу по «проторенному пути»: благодаря Мемнону, он уверовал в греческий военный гений и потому склонялся к назначению полководцем афинянина Харидема, заклятого врага Александра. Этот Харидем некогда сражался с Филиппом Македонским за Олинф, после разорения Фив был по настоянию Александра изгнан из Афин и нашел пристанище при персидском дворе. Он «посоветовал Дарию не делать опрометчиво ставкой свое царство: пусть он песет на себе тяжесть управления Азией, а на войну отправит полководца уже испытанной доблести» (Диодор). Харидем предлагал собрать войско численностью в 100 000 человек, треть из которых должны были составить наемники. Дарий почти согласился, когда вмешались сатрапы, которые обвинили Харидема в двойной игре: он, мол, добивается командования лишь для того, чтобы перейти вместе с войском на сторону македонян. Харидем отверг все обвинения и в гневе упрекнул персов в трусости «всеми словами, какие только пришли в голову». Дарий не снес оскорбления и приказал казнить грека. В результате царь царей остался без полководца, которому он мог доверять (сатрапы, все без исключения, безусловного доверия не внушали). Поэтому Дарии вынужден был лично возглавить войско; и первый его приказ лишил Фарнабаза наемников, составлявших ударные части персидского флота. Тем самым Фарнабаз утратил былое численное превосходство над Гегелохом и постепенно потерял завоеванные территории. А с точки зрения общей стратегии этот приказ означал, что персы отказались от попытки перенести войну на территорию Греции и собирают силы для решающего сражения с Александром в Киликии, на рубеже «исконно азиатских» земель.