追击大流士，是谁都能想到的，但此时进行追击却是十分危险的。大流士新败，却仍有巨大的不容轻视的战斗力。伊苏斯一役给波斯帝国的打击也比马其顿人所估计的要轻，大部分波斯骑兵在波斯的一些杰出将军的率领下，有秩序地撤退到波斯统治区内，驻扎在未被马其顿军占领的地区，并在当地招兵买马，很快就成为一股可观的力量。从战场上逃跑的大流士也很快在巴比伦集合起一支队伍。大流士虽写信求和，但也一直在作抵抗的准备。波斯人仍有一战之力，甚至仍有打败亚历山大的可能。
亚历山大深入波斯腹地作战，没有了像小亚细亚希腊城邦那样所给予的支持和欢迎，“解放”、“民主”和复仇等宣传也失去了作用，必然会遭到当地居民的顽强抵抗，马其顿军队有可能成为“一座在敌人领土上游移不定的小岛”（E.巴迪安）。深入波斯腹地作战更为困难的是，战线拉长，后勤供应更加难以保障。而后勤供应的好坏，正是亚历山大能否成功的关键所在。
对于亚历山大的后勤供应线来说，还有一个致命的威胁，那就是波斯海军。波斯海军一直是个使亚历山大头痛的问题。亚历山大没有可与波斯海军对抗的舰队，他原定的计划是在陆地上打击波斯海军，占领波斯海军的港口，征服大流士建造军舰和征集士兵的地方，这一计划由于亚历山大攻占了小亚细亚沿海的一些港口城市而取得了部分成功，但并没有解除波斯海军对亚历山大后方的威胁。腓尼基沿岸仍受波斯控制，波斯的腓尼基舰队已驶入爱琴海，正在寻找机会进袭希腊。希腊的斯巴达也仍然坚持和马其顿对抗。在这种情况下，在没有制海权的情况下，如果亚历山大率军向东深入波斯腹地，东地中海沿亚洲海岸线一带就有落入波斯海军之手的危险，后果是不堪设想的。亚历山大，一个伟大的军事家，当然不会这样去冒险。
亚历山大在对形势作了正确判断后，认为在追击大流士之前，必须摧毁波斯的腓尼基舰队。虽然他自己没有海军，但他确信，只要攻占了腓尼基诸城，夺取了腓尼基舰队的大本营和基地，波斯海军就会瓦解，舰队的水手就会弃船投奔他，因此他决定率军沿腓尼基沿岸南下，甚至推进到埃及，以便将整个东地中海置于他的控制之下，然后再去追击大流士。
亚历山大在南下之前，任命塞琉古为西里西亚总督、托勒密为地中海沿岸地区的总督，同时还保留他们在军队的职务。随后又任命米农为下叙利亚总督，并拨给他希腊联军骑兵，驻守该地。作了这些安排以后，亚历山大亲率大军向腓尼基进发。
腓尼基的沿海城市有20多个，它们虽然承认波斯的宗主权，却都是些与希腊城市一样的独立小王国。腓尼基人素以经商、航海和殖民著称，工商业十分发达，每个城市都是一个贸易中心，每个城市都有自己的舰队，彼此之间，充满矛盾和竞争。其中最重要的城市是西顿和推罗。这两个城市也是波斯帝国舰队的重要基地和港口。
亚历山大的进军，开始非常顺利。由于腓尼基人对波斯和大流士的统治不满，不少腓尼基城市对亚历山大持欢迎态度，同时，亚历山大大军压境，它们也无力抗拒。亚历山大先是得到了阿拉达斯岛及其附近地区的族长斯特拉唐的迎接。斯特拉唐一见亚历山大，就给他戴上一顶金冠，并把阿拉达斯岛和岛对面大陆上的一个繁华城市马拉萨斯献给他，属于自己势力范围的其他一些地方也一块交了出来。
随后，亚历山大又接受了比布拉斯和西顿的归降。在从西顿向推罗进军途中，又碰上了来迎接他的推罗代表。代表中有贵族，还有国王的儿子，他们告诉亚历山大，推罗全体市民已决定接受他的治理。亚历山大很高兴，称赞了他们，称赞了他们的城市。他让代表们回去告诉市民，他将去推罗城，向那里的赫拉克勒斯神庙献祭。
推罗城有一座古老的赫拉克勒斯庙，但这个赫拉克勒斯并不是亚历山大奉为祖先的那位。推罗人世代供奉的这位赫拉克勒斯，早在公元前14世纪就有了，而亚历山大奉为祖先的那位，则是数百年后底比斯王后和宙斯所生。还有另一个赫拉克勒斯，埃及人供奉的。埃及人认为他是十二神之一。这个埃及人供奉的赫拉克勒斯显然也不是被亚历山大当作祖先的那位。
不过，亚历山大准备去献祭的就是推罗城的赫拉克勒斯。当推罗的代表告诉市民，亚历山大要进城向赫拉克勒斯献祭时，推罗人坚决拒绝了亚历山大入城献祭的要求。他们让代表转告亚历山大，他们愿意接受亚历山大的一切命令，但决不能允许任何波斯人或马其顿人进城。
推罗人这种既不欢迎波斯人，也不欢迎马其顿人的态度，看似中立，其实是对亚历山大的挑战。推罗人之所以敢和刚打败波斯人的亚历山大对抗，一是因为他们有抵抗外敌的光荣传统，他们的城市曾经受住敌人一次又一次的围攻，巴比伦国王尼布甲尼撒曾围攻14年，而未攻破。这种传统激励他们不向任何强敌屈服。二是因为城池坚固，有恃无恐。推罗城在一个距大陆有半英里的岛上，有坚固的石头城墙，东面有两个港口，北端的叫西顿港，南端的叫埃及港。推罗人还有一支强大的海军和许多优良的作战器械。
亚历山大得到推罗人的回答，非常生气。他要求祭祖只是个借口，目的是要进城。推罗人不让他进城，就是拒不归顺他。如果不占领推罗这个腓尼基最重要的港口，他的计划就会落空。
他打发推罗的代表回去后，召集了他的部下将领，作对推罗宣战的动员，讲述了自己的计划和决定。他说：“朋友们，盟友们，只要波斯仍然掌握着制海权，我就看不出我们怎么能够安全地进军埃及。推罗现在态度暧昧，如果把它留在我们背后，同时埃及和塞浦路斯又仍在波斯手中，特别是由于希腊当前的局势，我们在这种情况下去追击大流士显然很不妥当。恐怕当我们率领全军进逼巴比伦和追赶大流士的时候，波斯部队很可能再把沿海地区占领，然后还要用更大的兵力把战争推向希腊。而在希腊，眼下拉斯地蒙人正与我作战；雅典现在虽还算安分，但也只是惧怕我方而不是亲近我方。不过，一旦我战胜推罗，就能占有整个腓尼基，而且波斯海军中最强大、最精锐的腓尼基这部分就有很大可能转到我方。因为就腓尼基的橹工和水兵来说，当他们的城镇已入我手之时，就不可能有勇气再为别人出海冒险。再进一步，塞浦路斯或者主动投降我方，或者我以海军袭击，轻易地把它占领。到那时，如果我方以马其顿舰队加上腓尼基海军控制海面，而且塞浦路斯又已在掌中，我方将稳操制海权。在这种情况下，我军再远征埃及将如探囊取物。得到埃及之后，即不必再担心希腊和我本国。到那时，国内既已安定，又有我们日益增长的威望，整个大海又和波斯以及幼发拉底河北岸广大地区完全隔绝，我们远征巴比伦即可毫无后顾之忧矣。”
亚历山大在这里对他为什么要南下腓尼基，为什么一定要攻占推罗，为什么要远征埃及，说得非常清楚。他的目的就是摧毁波斯海军，掌握制海权，稳固后方，以便远征巴比伦、追击大流士时，无后顾之忧。这就是他的南下计划。
2.最惨烈的一战：推罗攻坚战
为了坚定将士们夺取推罗的信心，亚历山大还声称他做了一个梦，他在梦里见赫拉克勒斯引导他进了推罗城。他的占卜师阿里斯坦德解释说，这个梦意味着推罗城可以攻下，但要付出很大的力气，因为赫拉克勒斯的成就是用力气取得的。而在另一方，据说，很多推罗人梦见太阳神阿波罗要离开他们到亚历山大那里去。为了不让阿波罗离去，他们随即把这位尊神的塑像绑起钉在坐垫上面，就好像阿波罗是个普通的叛逃者，在投向敌人时，被发现逮住了。这样两个梦反映了对阵双方的心态，有他们的希望、决心，甚至还有一些对对方的恐惧。推罗人的恐惧好像更大些，而希望却小些。
要攻占推罗城确是非常困难的，亚历山大决定先修筑一条从陆地通向推罗的宽200英尺的长堤。在进行这一工程中，亚历山大亲临现场，对工程的每一步骤都亲自进行指导，并不时发表鼓动性的讲话，还对干活特别出色的人给予奖励。开始时，由于近岸地区水浅，施工地区又在推罗人作战器械的射程之外，工程进行得很顺利。但当工程推进到接近推罗城时，水深已达18英尺，施工地区也已处于推罗人作战器械的射程之内，施工的将士不断遭到从推罗高耸的城墙上射来的排箭的袭击，更为严重的是，制海权仍掌握在推罗人手中，推罗人驾驶三行桨位战船不断向长堤攻击（这种三行桨位战船是古代常用的战船，由三组人，而不是三层人划桨，每组约有60名桨手，因此而得名。全长约120英尺宽20英尺，船头装有一个大金属撞锤，船上载有两栖作战士兵）。推罗人的战船一会儿冲击这边，一会儿冲击那边，使马其顿人的筑堤工程在许多地方都无法进行。
为了保护自己、控制局势，亚历山大令人在堤上修筑起两座塔楼，塔高达150英尺，与城墙等高，塔楼外层包上皮革以抵挡火箭，楼内安装石弩用以射击三行桨位战船。推罗人针锋相对，他们在一条大船上装满干柴、树脂、沥青和硫磺，在船头竖起两根桅杆，又在每根桅杆上栓上两根桁杆，桁杆上悬挂着装满易燃物的大锅。他们还在船尾压上重物，使船头尽量升高。风一起，他们就在船上放起火来，用战船拖着这着了火的船向长堤猛扑过来，转眼间，塔楼和长堤便都着了火，由于桅杆被火烧坏，大锅内的易燃物便全部倾出，塔楼和长堤的火势立即大得不可收拾。亚历山大马上命令从陆地这边把堤道加宽，以便在上面修建更多的塔楼，同时命令工匠制造更多的石弩。
这时，亚历山大已意识到，他必须有他自己的三行桨位战船，因为如果他没有自己的舰队，他就没法控制海面，而没有制海权，他就很难攻下推罗城。于是，他亲自率领一支部队去西顿和其他腓尼基城市，集合他自己的船队。而腓尼基沿岸各城市的国王，得知大流士在伊苏斯战败、自己的城市被亚历山大占领后，纷纷率领自己的舰队离开波斯舰队，来投靠亚历山大。很快，就有80艘腓尼基三行桨位战船和120艘塞浦路斯战船归降了亚历山大。为了能有更多的木材来建造更多的战船，亚历山大随后又率军进山，去采伐黎巴嫩著名的雪松。
在山中，亚历山大还曾冒死救出他青年时代的老师雷西马楚斯。在一次行军途中，天色已晚，他们两人沿陡峭的山路徒步而行，大多数马其顿人已走远，亚历山大不愿丢下年老体弱的雷西马楚斯。他可以看见远处敌人的点点篝火。夜里非常冷，他摸到最近的一堆篝火旁，刺倒火边的两个敌人，抓过一根燃烧的树枝，再跑回到自己那一小队人中，用这根树枝点起一堆大火，吓跑了敌人。亚历山大时常做出这样一些忠于友情和与部下共患难之事，反映了他深得人心的一面。