К юго-востоку от Сирии располагалась Финикия. Это приблизительно там, где сейчас находится государство Ливан. На протяжении многих столетий финикийцы считались величайшими мореплавателями в мире, и с их помощью персам удалось создать флот, который намного превосходил тот, что могли вывести в море македоняне и греки. Именно финикийцы строили персам корабли, и они же составляли экипажи этих судов, а главной военно-морской базой персидского средиземноморского флота был финикийский порт Тир. Если бы Александру удалось, вторгнувшись в Финикию, захватить этот город, тогда персидский флот оказался бы сильно ослаблен, а то и вовсе прекратил свое существование, лишившись своей основной базы. Как только Александр вступил на территорию Финикии, большинство городов сдались на милость победителя, однако жители Тира отказались подчиниться. И в январе 332 г. до н. э. македонская армия осадила город. С самого начала Александр понимал, что перед ним стоит трудная задача. Город был построен на острове и окружен мощными стенами. На море господствовал персидский флот, который исправно снабжал осажденных всем необходимым. Осада длилась шесть месяцев, однако в конце концов финикийские корабли из городов, подчинившихся Александру, выступили на его стороне и установили блокаду Тира со стороны моря. В июле начался штурм городских стен, македоняне ворвались на городские улицы, и в развернувшейся резне 6000 защитников города были уничтожены. Сами македоняне потеряли всего около 500 человек, но, следуя своей политике устрашения непокорных, Александр приказал распять на морском берегу 2000 жителей.
Флот Фарнабаза еще господствовал на море и мог бы при другом стечении обстоятельств еще долго оставаться проблемой для Александра, однако финикийские экипажи почти 200 кораблей, узнав об участи Тира, дезертировали и возвратились домой. Остатки персидского флота были разгромлены, сам Фарнабаз попал в плен и был отправлен в Финикию в лагерь Александра. Что с ним произошло дальше, представляет собой некоторую загадку. По одной из версий, персидскому флотоводцу удалось бежать, спрыгнув с корабля, когда тот стал на якорь возле одного острова, чтобы запастись провиантом. Однако ряд историков утверждает, что Барсина убедила Александра проявить в этом случае снисходительность и помиловать пленника, когда того доставили в Тир. Кстати, последняя версия представляется более вероятной, так как известно, что Фарнабаз перешел на сторону македонян; существуют документы, в которых сообщается, что он командовал одним из отрядов в армии Александра. Если эти сведения верны, тогда мы имеем еще одно свидетельство того, какое огромное влияние оказывала Барсина на своего великого возлюбленного. Можно не сомневаться, что если бы не она, то участь персидского полководца, доставившего столько проблем Александру, была бы иной.
К концу лета 332 г. до н. э. союзный флот захватил господство на море. Отныне Александр мог с легкостью снабжать свою армию всем необходимым и готовить ее к выполнению очередных задач. А следующей его целью стал город Газа, расположенный в 300 километрах к югу. Этот город находился в районе, чрезвычайно важном со стратегической точки зрения. Он контролировал узкую полоску плодородной земли вдоль восточного побережья Средиземного моря, по которой шли торговые пути из Азии в Африку. Захватив этот город, Александр открывал бы себе дорогу на Египет. Персидский царь, также понимавший значение Газы, приказал оборонять его любой ценой, тем более что сама природа облегчала защитникам эту задачу. Газа располагалась на вершине холма, имевшего высоту 80 метров, и македонские инженеры весьма сомневались, что его удастся взять штурмом, так как туда было очень сложно доставить осадные орудия. Однако Аристобул, главный инженер Александра, предложил полководцу план совершить подкоп под основание стен и обрушить их. На выполнение этого плана потребовалось почти четыре месяца, но в конечном итоге он полностью увенчался успехом: стены были разрушены, а затем последовал штурм города. Как и во всех подобных случаях, Александр решил примерно наказать непокорных жителей, но на этот раз действия македонян отличались особой жестокостью: все взрослые мужчины были убиты, а персидского правителя Батиса пытали на глазах у оставшихся в живых до тех пор, пока он не умер. Римский историк Курций пишет: