在德意志，年迈的路德维希·克拉普夫读了这封信的译文，他写信给伦敦的圣公会差会，敦促他们立刻行动，加入在非洲大陆中心对抗伊斯兰教的战斗。这时恰逢疟疾导致接连不断的死亡，热带非洲的传教活动再次陷入低潮的时刻：1875年初去世的查尔斯·纽是新近的死亡人员，他是一名工人，也是一个有社会主义理想的卫理公会派教徒，他生活在乞力马扎罗山附近的聚居区，还由于是第一个攀登到乞力马扎罗山雪线的欧洲人而被称颂。
各方对斯坦利的挑战的回应热情非常强烈，以至于利兹市的百万富翁隐士罗伯特·阿辛顿提议，如果克拉普夫任领队，他将资助一支基督徒探险队前往布干达。克拉普夫拒绝了他的提议，他知道他的旅行时代早已过去，但是其他人勇于尝试。在六个月之内，先锋队伍抵达桑给巴尔。但是，抵达布干达则是另一回事了，在斯坦利吹响号角过去整整三年，第一个到达那里的是一名新教徒，他是顽固的苏格兰人亚历山大·麦凯。他的几个同伴被杀或死于热疫，其他人因病返回英国，还有很多人会在十年里付出最后的代价。
英国圣公会差会还有另一个危机要应付。罗马天主教突然也想要赢得中部非洲的核心，所以1878年6月，一支由十个白人神父组成的队伍从桑给巴尔对岸出发，向布干达进发。他们足够显眼，因为他们穿着僧侣长袍，脖子上戴着的诵经用的念珠还坠着十字架。五百名搬运工和火枪手组成了这支旅行队，它的规模展现了他们的决心。大部分白人神父是法国人，这也是为了震慑英国人。争夺非洲的宗教战打响了。
在欧洲有机会对他的信件做出回应之前很长时间，斯坦利从布干达继续向前推进。向西南方向朝坦噶尼喀湖行进时，他穿过了米兰博的领地，米兰博是他在穿越非洲的旅途中遇到的三位具有历史影响力的领袖中的第二位。五年前，他去坦噶尼喀湖寻找利文斯通时，他差点遇到这位伟大的尼亚姆韦奇人的战争领袖。之后，他在塔波拉的阿拉伯人的诱惑下，在战争中帮助他们对付米兰博。斯坦利只参与了一场小规模战斗，因为他的主要目标还是继续前行寻找利文斯通。但是，对于那个时候几乎不为人所知的米兰博，他仍收集了足够多的信息，他称米兰博为“非洲的拿破仑”，他还将米兰博描述为一位聪明的年轻首领，有偷盗行径和在丛林作战的天赋。
1871年，米兰博几乎占据这一地区主要的阿拉伯人据点塔波拉，他烧毁了大部分房屋，获得大量象牙。他还伏击并杀死了塔波拉最卓越的居民——阿曼商人哈米斯·本·阿卜杜拉。此前哈米斯曾发誓杀死米兰博，就像几年前他将尼亚姆韦奇人的首领“反叛者”马努阿·塞拉斩首那样。
斯坦利在《我如何找到利文斯通》一书中对米兰博的记述早就给出了暗示，这位有着非同一般才干的非洲领袖统治着坦噶尼喀湖东北方的广阔区域，并且像他不幸的前任马努阿·塞拉一样，试图打破阿拉伯人的商业垄断。他的部分军队有传统的恩戈尼战士（被斯坦利称作可怕的“鲁加-鲁加”）的后裔。
后来，更多关于米兰博的事实传到桑给巴尔，那里的外国领事馆仔细研究了这些信息：他的真实姓名是麦耶拉·卡桑达，他出生于一个显贵家族，20岁时，他开始用假名“米兰博”称呼自己，意为“尸体”，以作为对他敌人的一个冷酷警告。他身材高大，仪表堂堂。他很早就意识到无法只依靠长矛就驱逐阿拉伯人，所以他用火枪武装他的战士，用象牙购买大量火枪或者靠劫掠阿拉伯人的商队来获取它们。
桑给巴尔的苏丹焦急地想要对抗这个精力充沛的异教徒敌人，以保护他在大陆的统治领地，他派出一支三千人的队伍前往塔波拉，这支队伍主要由来自俾路支的雇佣军构成。由于缺少食物并且领导不力，苏丹派出的作战队伍没有取得什么进展，但它耗费了十万银币，苏丹不得不提高桑给巴尔的象牙和丁香的税收，以偿付这笔开支。
米兰博明显的弱点是缺乏武器，所以苏丹在沿海对武器实行严格封锁。1874年初，给苏丹出这个主意的英国领事自满地向外交部报告，米兰博“完全没有弹药”，不再需要害怕“他或者他的追随者”。但是，米兰博生存了下来。他统治的松散帝国从维多利亚湖的湖岸一直延伸至坦噶尼喀湖的最南端。这个时候，他宣布与阿拉伯人休战，但是他希望趁此时机，能够从自己的族人和他的臣属中召集起一支七千人的队伍。
1876年，当斯坦利见到他时，米兰博已接近他攫取的权力巅峰。他的首都乌兰博是一个拥有几千居民的城镇。他从乌兰博向外进军的消息，吓坏了斯坦利当时旅行正经过的乡村的村民，但是“非洲的拿破仑”并不醉心于战争。他只是热衷于揣度经过他的领地的白人。米兰博派出三名使者打头阵，他们是他的侍卫，这几个人穿着蓝色和红色外套，戴着白色长头巾，询问斯坦利是否愿意与他会面。斯坦利回答，他将“满怀喜悦，和酋长结成亲密的友谊”。
在他们初次握手之后，斯坦利觉得他自己“已完全被这位非洲绅士迷住”，米兰博与那些阿拉伯人留给他的印象完全不同。他在日记中写道：
今天对我而言将是难以忘怀的，因为我拜访了著名的米兰博……他身高五英尺十一英寸，大概35岁，身材匀称，没有一丝赘肉，相貌英俊，五官端正，讲话温文尔雅……他外表温顺谦逊，目光平和，言语亲切，丝毫没有表现出五年来他在非洲中心展现出来的拿破仑般的天才。
那天晚上，他们歃血为盟。每个人都在右腿膝盖稍微往上的部位切开一个小口子，接了一些血，擦在另一个人的伤口上。他们一起宣誓：如果兄弟之情破裂，“那个人将被狮子吞噬，被毒蛇毒死，自食苦果，朋友也将离去，枪支将伤害他自己，一切厄运都将伴随他，直至死亡”。第二天，他们各自继续走自己的路，米兰博送给他的新兄弟五个护卫，以确保他不会因被索取税金而有所延误。而斯坦利的告别礼物是一把手枪和一些弹药，很有代表性。
他是第二个见到米兰博的白人，只是因为他的名声更响亮（以及最终的悲剧），使得人们更多地把注视的焦点放在他身上。第一个见到米兰博的白人是年轻的瑞士象牙商人菲利普·布鲁瓦永，他在几个月前冒险进入内陆。米兰博赠予他一所房子和一个妻子，并且邀请他在乌兰博定居。斯坦利在行进途中听说了布鲁瓦永，向他求助获取各种东西，包括蓖麻油和泻盐。布鲁瓦永给他寄回了蓖麻油，还有两块橄榄皂，以及几份六个月前的《费加罗报》。
六个月之后，斯坦利到达坦噶尼喀湖西边的曼耶玛国。他即将进入最糟糕的旅行阶段。他知道如果他能够抵达非洲最后一条地图上未标明的大河刚果河的主航道，并且沿着它抵达大海，他就将创造历史。但是他的尝试也可能带来死亡，与他一起探险的一百五十个幸存者中包括他的几个妻子和孩子，以及与他一起开始这场远征的三个白人助手中唯一还活着的弗兰克·波科克。这时候，探险队进入了一片密林，沿着一条阴暗泥泞的河流前行，他们可能最终到达刚果河。
斯坦利当时的恐惧不是面对这片完全未知的陆地，而是害怕他的人几乎都要逃跑。他们到达了几个猎获奴隶和收集象牙的内陆定居点，它们由阿拉伯人和斯瓦希里人经营。逃亡者可以在开始返回桑给巴尔的长途旅行之前，轻易地躲藏在这些定居点里。他唯一使得远征队一同前进的机会是在行进的过程中找到方法错过定居点，当定居点远到他们如果返回就很可能被树林中的敌对居民杀死时，他们就只能选择继续前行。
蒂普·蒂普能够将斯坦利从窘境中解救出来，前者的真实姓名是哈米德·本·穆罕默德。这位象牙贸易的主导者是19世纪后半叶中部非洲内陆三位最有权力的人物之一。他年轻时是一个典型的奴隶猎人，他在回忆录中记述了多次猎捕活动，其中一次活动就清楚地表明了这一点：“我深入到扎拉姆国的每一个地方，在五天的时间里捕获了八百人。他们称我为‘金古格瓦’（kingugwa，意为猎豹），因为猎豹到处任意攻击猎物。我给他们戴上镣铐，带着他们回到姆坎巴。”在他见到斯坦利时，他的名声和财富使他几乎可以行使苏丹的权力。他为前往海岸地带的商队招募了两千多名搬运工，每个搬运工都背着一颗象牙。
蒂普·蒂普的外号源自他的枪声，在某种程度上，他比穆特萨或者米兰博都更重要。他活了很长时间，在面临无法阻挡的欧洲人进军时仍然徒劳地想保住他的庞大领地。直到这件事没有任何希望，他宣称自己是遥远的桑给巴尔苏丹的真正臣属，并且坚称他的土地属于苏丹的帝国。
斯坦利曾在一个更为遥远的阿拉伯定居点遇到蒂普·蒂普：“他个子很高，蓄着黑胡子，肤色很黑，正值盛年，身材挺拔，动作敏捷，一副精力充沛的样子。他的面相很聪慧，只是眼睛不时神经性地抽动一下。”会见欧洲人对蒂普·蒂普而言并不新奇。他几乎在桑给巴尔长大，在他旅行进入内陆期间，他遇到了利文斯通，给过后者食物，在返回海岸地带时，他还帮利文斯通带信给英国领事约翰·柯克爵士。近来，他还帮助海军军官弗尼·洛维特·卡梅伦寻找一条安全通往安哥拉的道路。
尽管蒂普·蒂普具备阿拉伯人的所有礼仪和想法，但是他的根仍在非洲。他的祖先数代居住在斯瓦希里海岸（他们与19世纪40年代抓住机会跟随赛义德·赛义德来到桑给巴尔的阿曼的阿拉伯人非常不同），他的祖母是一个奴隶。他父亲的第二任妻子是一位非洲酋长的女儿。他把米兰博当作自己的朋友，尽管阿拉伯人阴谋挑拨他们之间的关系。他们之间相互尊重，达成永不与对方作战的协定，因为他们两个人隔着坦噶尼喀湖遥遥相对，都是湖岸边大片领地的统治者。
在1876年10月斯坦利见到他时，蒂普·蒂普已经9年没回桑给巴尔了，但是他定期派商队运载象牙和奴隶前往海岸地带。印度穆斯林商人领袖塔里亚·托潘，在桑给巴尔为他积聚财富。给蒂普·蒂普留下深刻印象不是一件容易的事，但是斯坦利和他第一次见面之后就成功做到了。在回忆录中，蒂普·蒂普这样写道：
第二天早上我们去见他，他向我们展示了一杆枪，告诉我们：“这杆枪可以射出15发子弹！”我们还没见过能发射15发子弹的枪支，也没有人知道有这种枪。我问他：“从一个枪管里吗？”他说是从一个枪管里射出的，所以我让他现场试射以便我们可以见识一下。但是，他说他射击一次要花费20—30银币。我认为他在说谎……我对他说：“在鲁马米有一张弓能射20支箭。当你开弓时，20支箭一起发射，每支箭杀死一个人。”他听说之后走到外面射击了12次。之后，他用一把手枪射击了6次。他回来坐在露台上，我们对此惊讶不已。
这个事件之后，斯坦利很快和蒂普·蒂普达成一份协议：如果蒂普·蒂普的人随同他的队伍一起远征两个月，他将向他们提供一笔价值5000玛丽亚·特蕾西亚银币的巨款。这笔钱以及对他勇气的挑战形成了双重诱惑，使得蒂普·蒂普难以抵抗。他的家庭成员努力劝阻他：“什么，和一个欧洲人一起走，你是疯了吗？你有大量象牙，为什么还要跟随一个无信仰者？”蒂普·蒂普让他们管好自己的事，然后和斯坦利签订了协议。几天后，他们就出发了，他们中一部分人乘坐独木舟，岸边悬伸出来的树枝投下阴影，使得河面显得比较阴暗，还有一部分人沿着河岸进发。他们与敌对的村民进行了一系列交战，对方从茂密的树林里向他们发射毒箭，但是他们继续前进。
蒂普·蒂普的人与远征队离别的重要时刻来临。蒂普·蒂普警告斯坦利远征队的人，如果他们有人在他返途时试图跟着他到达坦噶尼喀湖，他“一定会杀死他们”。蒂普·蒂普在回忆录里曾提及这个事件，但是斯坦利没有记述这件事。他则绘制了一幅他们在离别前夜于丛林空地尽情欢庆的画，这场庆典以享用大米和烤羊肉等美食圆满结束。第二天一早，1876年12月28日，当远征队的成员划着独木舟进入“未知地域闪闪发光的入口”时，斯坦利透过树林，隐隐约约听到蒂普·蒂普的人唱诵的告别歌曲。
在这场长达10年的旅行中，整个非洲的历史轨道都将有所改变。