Им приходилось возвращаться на свои позиции в виду города, но, когда воды стало не хватать, персы снялись с якорей и ушли прочь. Александр же решил распустить основные силы военного флота ввиду дороговизны последнего и в качестве альтернативного подхода захватил города и порты не берегу, которые персидские моряки могли бы использовать как базы и/или как источники получения снабжения. Лишая врага безопасных убежищ и способности пополнения всего необходимого, Александр снижал вредоносное воздействие персидского флота. Роспуск собственной эскадры мог бы показаться рискованным предприятием в краткосрочном плане, но Александр умел считать и смотрел вперед, видя конечную точку своих стратегических замыслов.
Самым важным городом и базой снабжения по соседству с Милетом являлся Галикарнас. По всей вероятности, наиболее надежно укрепленный город в Малой Азии, он находился словно бы в естественном амфитеатре и защищал себя несколькими сильными цитаделями. Незадолго до войны обороноспособность города усилили за счет рва более 13 м шириной и около 7 м глубиной.
Мемнон Родосский, удостоенный Дарием всей полноты командования на западе, собрал для защиты крепости греческих наемников из ближайших городов, а ввиду отсутствия у Александра способов блокировать город с моря, защитники его могли получать все необходимое водным путем. Поскольку персидские эскадры прикрывали город с моря, Александру приходилось разворачивать наступление с северо-востока или с запада. Источники преуменьшают тяготы осады, но она, как бы там ни было, продлилась два месяца, при этом в штурмах и обороне города стороны опробовали все приемы и методы, известные осадному делу античного мира. Вначале Александр немного медлил, ожидая подвоза осадной техники к Галикарнасу. После неудачной попытки взять городской порт примерно в 20 км от самого города, Александр велел воинам заваливать ров перед стеной при посредстве предназначенных специально для этих целей «черепах». Заполнив рвы, осаждающие смогли приступить к подтягиванию к стенам осадных башен. Чтобы заставить защитников пригибать головы и не особенно мешать сравнивать с землей участки стены, македоняне применяли катапульты. Обороняющиеся не пали духом и устраивали ночные вылазки, затем прикрыли проломленный участок куртины внутренней блокирующей штурмующим путь стенкой. Ночной приступ на эту новую преграду, вероятно вдохновленные обильными возлияниями, защитники отразили, и в первый и единственный раз за всю историю войн Александра ему пришлось просить о перемирии для выноса убитых и предания погребению их тел.