天下没有不透风的墙，优素福听到风声，派了一位特使来到埃及，要求总督禁止哈米德离境，1804年12月，还让儿子和哈米德12岁的长女结婚。

      哈米德招兵买马，伊顿也在亚历山大招兵，最后组成一只联合国军，人员包括希腊人、意大利人、的黎波里人、阿拉伯人、埃及人、法国人、美国人和英国人等11国人，400多人的队伍中美国人只有十人，伊顿、海军陆战队中尉普雷斯利·奥柏那、海军陆战队士官长阿瑟·坎布尔和六名海军陆战队士兵，以及阿古斯号的少尉帕歐里·派克。

      海军陆战队在当时籍籍无闻，巴巴里战争中，海军陆战队参加了夺取费城号和夺船行动，但从来没有陆战的经历。

      这400人的部队有25名炮兵，可是没有一门炮，由一位土耳其人指挥。步兵38人，主要是希腊人，哈米德召集了90名的黎波里人，还有300左右阿拉伯骑兵和步兵。107只骆驼携带口粮、饮水和装备。部队的服装更是五花八门。伊顿要求海军派遣100名海军陆战队，加上100人的装备，但海军不答应。

      1805年2月23日，伊顿和哈米德签署协议：美国支持哈米德复位，哈米德答应复位后释放费城号被俘人员，用从丹麦、瑞典等国拿到的保护费作为给美国的赔偿，给予美国最惠国待遇，再也不收美国的保护费。双方同意由伊顿担任将军，指挥这只杂牌军。

      1805年3月8日，部队出发。

      行军路线沿着地中海西去，杂牌军一出发问题就出来了，伊顿找来的人还成，哈米德手下那些有心复仇的人也成，关键是占大多数的阿拉伯雇佣军，这帮人一来冲着钱来的，二来和欧洲人还有宗教冲突。二天后，牵骆驼的和阿拉伯步兵就罢工了，要求马上就支付原定的每头骆驼11美元的费用。伊顿拒绝现在支付，阿拉伯人不走了。

      不走了，好吧，伊顿下来基督徒返回亚历山大，行动取消。阿拉伯人屈服了，继续前进。

      三天后，传来消息，德尔纳起义了，准备欢迎哈米德。听到这个消息，阿拉伯骑兵鸣枪庆祝，走在后面的阿拉伯步兵以为受到攻击，打算抢劫供给后逃跑，几乎造成自相残杀。

      又过了两天，海军陆战队帐篷里食物和武器被盗，害得海军陆战队从此枕着武器睡觉。

      不久，牵骆驼的又不走了，这次伊顿拿出仅有的533美元，又向手下借了140美元，才说服了他们。可是当天晚上，大部分骆驼都不见了，几位雇佣军头目联合起来，要求先派人到邦巴，确定美国军舰等在那里后再行军。而且又有消息传来，优素福派出800骑兵，前来增援德尔纳，于是他们更有理了。伊顿下令给阿拉伯人断粮，而且扬言有美军增援，这样找回了50头骆驼，继续前进，遇到了一个阿拉伯部落，有200多名战士加入了他们的队伍。人多了，可是粮食和饮水越来越少，而且新的危机出现了。

      听说优素福派出援军，哈米德胆怯了，决定放弃这次行动。伊顿再次采取断粮的办法，并说服了哈米德。伊顿的毅力感动了哈米德，他不仅克服了自己的胆怯，而且还昼夜奔驰上百英里，把逃跑的人劝回来。

      进入的黎波里后，伊顿开展了西方人在北非从来没有人采取的战术：攻心为上。在宣传哈米德是合法的君主的同时，大力宣扬美国人是友好的，是来解救的黎波里的。这个战术非常成功，虽然阿拉伯雇佣军逃跑了不少，很多本地人前来投靠，到了四月初，他手下有将近700名战士，外加500多名追随者。

      然而，队伍中基督徒和阿拉伯人的矛盾并没有得到缓解。4月8日，出发整整一个月的那一天，冲突到了一触即发的关头。