亚历山大一直试图找出连接波斯和印度的道路，不管是陆路或者海路。过去历史上许多有名的君王也曾做过这项尝试。这次亚历山大从印度回返希腊，就希望在海陆两方面分头并进，他派遣船队，希望能开辟出新的航路。舰队的指挥官是非常能干的纳亚鲁克斯，他带领的船队沿着西边前进；亚历山大所率领的军队则从陆路而行，反而成了舰队的支援部队。
公元前325年8月底，亚历山大率领的军队先行出发，舰队预定在港口停泊，以便得到陆路部队的食粮补给。一行人一路西行，每走一步，帝国就近了一步，可是谁都没有想到他们却是一步一步地迈向死亡。
出发之后，军队时时遭到当地民族的反抗，亚历山大花了一个月的时间加以平定。到了克卡拉的地方给予舰队第一次补给，并且在那里扎营，此后，大军就离开了海岸往北走。这一带是内陆部分的沙漠地带，阳光灼热，风沙满天，连当地的向导都会迷失方向。全部的路程大约是三百公里，沙漠上的艰苦行军却耗费了两个月之久。沙漠里白天的气温超过38℃，因此只能在夜间行军，靠着天空中大熊星座和小熊星座以辨认方向。
沙漠中行军实在艰苦，饮水补给的地点间隔愈来愈远，而且水源愈来愈少。原来一天行军二十公里，最后必须加紧变成二十五公里。
将士们在沙漠中忍受着饥饿和口渴，刺眼的阳光使人睁不开眼睛，又干又烫的沙漠像海一样无边无际地展现在眼前，即使是年轻力壮的将士们也受不了这种肉体的折磨。比军队人数更多的妇女们跟随在这些队伍的后面，她们的命运是可想而知的：这块大沙漠终究要成为她们埋骨的地方。当时悲惨的情景真是笔墨难以形容的！
沙堆像小山似的起伏着，茫茫的一片黄沙展现在眼前。当脚踏下去时，人就陷进了柔软的细沙之中，就像陷进了泥沼，或者说陷入了盈尺的积雪中。
许多身体衰弱的将士一个个落在队伍的后面，有的是因为太过疲劳，有的是得了热病，有的是耐不住饥渴，终于相继地脱离了队伍。大家都自顾不暇，所以没有一个人会留下来照顾他们、陪伴他们，只好让他们在沙漠里自生自灭，等待死神的召唤。
许多载满了东方名贵稀罕的珍珠财宝的车辆最后也被遗留在沙漠里。他们把马杀了当食粮，这是不得已的办法。一旦发现了水源，将士们就迫不及待地跑去痛饮一番。在严重脱水的情况下，急遽地喝下大量的水，结果只能是当场胀死。
在这种情况下，亚历山大何以能够牢牢地统治军队呢？当时有一个传说，有一个将士捧着非常珍贵的一碗水要递给亚历山大，但是区区一杯水如何能分给眼前的兵士们呢？亚历山大不忍心喝它，毅然地把得来不易的这碗水倒在热沙中，他那种愿意和将士们共甘苦的决心深深地感动了每一个部下。大家顿时精神大振，好像喝下了这一碗水似的。
亚历山大的军队慢慢地走出了沙漠，沿着西北的草地前进，不久就到达塔鲁马尼亚的首都。亚历山大下达紧急命令，叫当地的郡守来迎接，并送来许多救援的物资。大军在这里充分地休养了一百天之久。到这时，原来浩浩荡荡的队伍已经没有多少人了，他们抛弃了不少的金银财宝和日常用品，甚至丢掉了作为军人第二生命的武器。至于与大军同行的妇女们，则早已成了沙漠中的冤魂了。
克拉得罗斯率领的另一支军队朝东北的山地往下走，正好遇到亚历山大所率领的大军。自从在印度河分手之后，这还是第一次会合。亚历山大的海上部队经过长期的航行，也在此地与他会合了。三支部队同时会师实在是出人意料。
纳亚鲁克斯的舰队等到东北季风来临的时候，就从印度河口的港口出海，大约9月21日前后依照预定计划抵达亚历山大港停泊，当地的居民筑着堡垒不让他们靠近，同时还袭击他们。9月24日遇到顺风，于是舰队又再度出海，预定是10月下旬再停泊另一个港口。每一艘船上只带了十天的食粮和五天的饮水，他们的食粮补给全依赖亚历山大的陆军部队，可是自从亚历山大的军队转入内陆之后，在沙漠中发生了空前的悲剧，因此对海上的补给也中断了。舰队的困苦情形可想而知。在缺乏补给的情况下，他们沿着荒凉的海岸靠自己去寻找食物，当时的情况在航海日记中有十分详尽的记载。尽管纳亚鲁克斯所率领的舰队要为生存奋斗，可是他们还是没有忘记探险的任务。在沿岸的地区有一些过着原始生活的土著们引起了他们的注意。这些人是以打鱼为生，而且都是生食；酋长住的小屋非常别致，是用鲸鱼的筋骨和贝壳很巧妙地建造成的。
当这些希腊的船员第一次看到海中的鲸鱼时，一个个都吓得目瞪口呆，他们简直不敢相信世界上竟有鲸鱼喷水这么怪异的事情。纳亚鲁克斯告诫部下要镇静，并且将船向怪鱼的方向驶去，他们有的敲打器皿，有的吹喇叭，有的将船桨在水面上乱拍，以此吓退鲸鱼。
经过了饥饿和不安的两个月后，船员们仍能维持原有的秩序，这都归功于纳亚鲁克斯临危不乱的沉着和冷静，使船员们对他产生信赖感。
到了12月，波斯湾口的阿拉伯半岛已经出现在眼前，于是他们改变方向，朝海峡的更深处航行，并且在港口抛锚休息。这块土地除了没有橄榄树外，非常酷似故国希腊，水草丰美，果实累累，景色非常秀丽。纳亚鲁克斯曾在航海日记上写下了简短的感想。
船员们又饿又渴，他们到达港口时，当地的人民以奇异的眼光非常警戒地看着他们，使船员们感慨颇深。他们日夜盼望能够早日回到希腊的克里特岛，如今面对着酷似故乡的景色，正好聊慰思乡之苦。
船员们相继登陆到各处去看看，同时也调查内陆的情形。纳亚鲁克斯带着六名部下往内陆走去，这时突然发现一个身穿希腊服，口操希腊语的男子！
原来这个人也是亚历山大的将士，他告诉纳亚鲁克斯说，亚历山大扎营的地方离此只有五里的路程，纳亚鲁克斯听了极为兴奋。这个消息很快也传到了亚历山大的耳朵里，他简直难以相信有这么巧的事！可是经过了沙漠里的折磨，他现在所剩下来的物资几乎等于零，他当初答应要给舰队补给的承诺现在却无法兑现，心中感到非常痛苦，并且自责不已。
纳亚鲁克斯和亚历山大再度相逢，彼此兴奋异常，恍如隔世！亚历山大几乎无法认出这个蓬头垢面、衣衫褴褛的人就是他的海军指挥官。离开了贵族和身边的大臣及卫兵们，当他单独面对着这位海军指挥官的时候，他把右手放在纳亚鲁克斯的肩上，再也控制不住自己的感情，继而悲从中来，和纳亚鲁克斯抱头痛哭，好不容易才逐渐控制住激动的心情。亚历山大对纳亚鲁克斯说：“只要你们平安地回来，我就感到非常高兴了，船只和船员们的情形如何？”
纳亚鲁克斯回答：“船只和船员们都平安地跟着我。”
亚历山大听了大喜过望，又高兴地流下了眼泪。他怎么也没想到，船只和船员在食粮不继、航路不熟的情况下还能够安然无事。
亚历山大很恳切地说：“你知道吗，我听到你们全体都平安无事，比我征服了整个亚洲还要高兴百倍！”
亚历山大不忍心让纳亚鲁克斯再航行到波斯湾，他打算换一名指挥官，可是纳亚鲁克斯一再地恳求让他完成任务。这不但是他的责任，也是他的荣誉。他这种忠诚执著、不畏艰险的精神宛如亚历山大的翻版。