在伊苏斯战役后，亚历山大面临着是去追击逃跑的大流士三世，还是去占领腓尼基和埃及，以解除自己的后顾之忧这样一个两难的选择。因为当时波斯帝国的海军还相当强大，如果去攻击希腊，会引起对亚历山大不满的希腊人的起义，从而使亚历山大的后院起火；或攻击空虚的马其顿，这也是亚历山大十分担心的。因为这并非空穴来风，在不久前，迈农曾经企图这么做过。当时迈农奉大流士三世之命率领迈农自己的雇佣军和波斯的全部海军，去攻击希腊和马其顿。只是因为迈农死了，才使亚历山大免去这一劫。但这并未完全消除亚历山大的担忧。因此，亚历山大决定先去夺取腓尼基和埃及，以消除自己的后顾之忧。

亚历山大从马拉萨斯出发，一直南下，一开始很顺利。他接受了腓尼基的毕不罗斯和西顿的归降。据说，西顿是自动迎接亚历山大进城的，因为那里的人们“极其厌恶波斯人和大流士”。但在推罗，亚历山大却遭到了坚决的抵抗。虽然，当亚历山大向推罗进军时，推罗人也曾派了代表在半道上去迎接亚历山大。这些代表说，推罗全体市民已决定接受亚历山大的治理。亚历山大也称赞推罗这座城市和他们的代表，要这些代表回去告诉推罗的市民，说他打算到推罗去向赫丘力士神献祭。推罗的代表们回去把亚历山大的话向市民宣布后，推罗的市民说，他们“接受亚历山大的一切命令，但决不能允许任何波斯人或马其顿人进城”。[7]推罗人认为，他们的这个决定在当时是最妥善的。但亚历山大听到这个话以后却大冒肝火，他召集他的“伙友”们、部队的司令以及其他军官开会，鼓动他们攻打推罗。

推罗是腓尼基地区的一个重要城邦。在历史上，腓尼基地区没有形成一个统一的国家，而是形成了若干个独立的城邦：毕布罗斯、西顿、推罗等。因此，这里成为周围强国侵略和入侵的对象。推罗这个城市“位于一个海岛上，四周筑有高耸的城墙，使它更加难攻；而且，在附近的海面进行的任何军事活动都只会对推罗人有利，因为波斯军队仍然掌握着制海权，推罗人也还保有大批战船”。[8]亚历山大决定由陆地修一条堤通往推罗。这一带海峡很浅，附近又有大批石头和木头，因此，在泥里打桩应该是很方便的。开始时筑堤工程进展很顺利，但当他们推进到接近推罗城时，水也越来越深，推罗人从高高的城墙上射来的箭使他们很难办，而且推罗人还掌握制海权。但后来亚历山大从西顿等地调来海军，并用擂石器抛掷石头。推罗人进行了英勇抵抗。不过，他们虽然在与亚历山大军队的对峙中取得过一些胜利，但终于被亚历山大的军队攻破了城池。远征军对推罗人进行了血腥的屠杀。阿里安说：

由于围城太久，马其顿人的火气早已按捺不住了；更因为推罗人曾活捉了从西顿坐船来的一些马其顿人，把这些俘虏拖到城墙上，故意叫在营地的希腊人都能看见，就这样在众目睽睽之下把他们砍死并扔到海里。这更激起了马其顿人的万丈怒火，因此，他们不论看到什么人都狠命砍杀。有八千推罗人被砍倒在血泊里。

马其顿人“在整个围城战役中，总共大约有400人牺牲”。[9]有一些推罗人逃到赫丘力士庙里，他们都是推罗的要人，其中包括国王阿则米卡斯，还有一些迦太基来客，被亚历山大赦免。其他人则都被当奴隶出卖了，一共约有3万人被卖为奴隶。[10]

在攻占了推罗后，巴勒斯坦的大部分都投到了亚历山大一边，只有一个加沙城例外。加沙城很大，建在高岗上，四周的城墙很牢固，是从腓尼基通往埃及路上在沙漠边缘上的最后一座城市。当时有一个名叫巴提斯的宦官占据着加沙城，有一支由阿拉伯人组成的雇佣军，而且储备了大量的粮草，打算长期死守。在这里，亚历山大又遇到了顽强的抵抗，他本人也被射伤。该城被攻破后，“加沙市民还是抱成一团顽抗。每个人都在自己的岗位上战斗到底，结果全部被歼。亚历山大把他们的妇孺都贩卖为奴”。[11]

在占领了加沙之后，亚历山大便率领远征军前往埃及。第七天到达埃及境内的白露西亚。他的舰队从腓尼基出发，沿岸和陆上的部队齐头并进，也已到达白露西亚。当地的波斯官吏马扎西斯拱手让亚历山大进了城。亚历山大一边派兵驻守白露西亚，一边命令海军沿尼罗河上溯直到孟菲斯。他自己则率部到赫拉奥波利斯。然后，他又乘船沿尼罗河顺流而下，到达后来以他的名字命名的地方上岸，觉得在这里修一座城市非常理想，于是，在他的命令下，建造了一座亚历山大里亚城。

据说亚历山大打算把城墙的具体位置在地面上勾画出来，留给筑城的人按线修建，但找不到画线的材料。后来有一个准备参加筑城的人异想天开，出了一个好主意：把士兵们随身用容器盛着做口粮用的粗粉收集起来，国王在前面走，后边跟的人就往地上撒，走到哪撒到哪。就这样，亚历山大设计的围绕市区的那道城墙的具体位置就算划出来了。[12]

在埃及期间，亚历山大曾去拜访过利比亚沙漠中的阿蒙神庙，

一个原因是他打算去问卜，因为阿蒙的神谕被确认为总是千真万确的……另一个原因是……想对他自己了解得更准确一些，至少他事后可以说他对自己了解得更清楚了。[13]

据阿里安说：

阿蒙庙所在地区极目四望，一片荒凉，茫茫沙漠，滴水难得。但庙宇周围小小的中心地带（最宽的地方约有40斯台地），却是绿树成荫，有橄榄、棕榈等树。在所有这一带地方，只有这一处能有露水。还有一股泉水从地下涌出。这口泉和一般从地下冒出来的泉水大不相同。它冒出来的水一到中午，喝起来就非常清凉，用手一摸更觉得凉爽，简直凉到不能再凉了。但一到傍晚太阳落的时候，水就开始暖起来，越晚越暖，到半夜最暖。半夜以后就又慢慢变凉，天亮时就已经凉了，到中午时最凉。一年到头，每天都是这样循规变化。这一带还产天然食盐，是从地里采掘出来的……亚历山大视察了这个绿洲，赞不绝口。他还祈求神示，据他自己说是得到了他梦寐以求的那种回答，然后就回埃及了。

去绿洲中的阿蒙神庙，亚历山大是沿着海岸一直走到帕拉托尼亚，然后转入内陆，向阿蒙神庙走去，路上一片荒凉，大部分是沙漠，无河水。途中，军队迷了路，连向导都不知道往哪儿走。据托勒密记载，是两条蛇指引了路；而阿瑞斯托布拉斯记载说是由于一只鸟引的路才使亚历山大走出了困境。至于从绿洲回来，阿瑞斯托布拉斯说他是由原路回去的，但托勒密却说他走的是另一条直奔孟菲斯的路。[14]

在孟菲斯，他接见了从希腊来的一些代表团，补充了军队，整顿了埃及的政务。他把全埃及分为两个省，分别任命埃及人多劳斯皮斯和坡提西斯为省长，但坡提西斯不愿就任，于是就叫多劳斯皮斯统辖全境。此外还任命了由希腊人担任的驻军司令等。

公元前331年春，亚历山大率领远征军离开埃及继续他同波斯人的战争。他途经尼罗河三角洲、西奈半岛、巴勒斯坦和叙利亚，到达两河流域，穿过幼发拉底河和底格里斯河，来到两河流域北部地区。在这里的高加美拉，公元前331年9月，远征军和波斯军队进行了最后一场大战——高加美拉之战。