在德意志，年邁的路德維希·克拉普夫讀了這封信的譯文，他寫信給倫敦的聖公會差會，敦促他們立刻行動，加入在非洲大陸中心對抗伊斯蘭教的戰鬥。這時恰逢瘧疾導致接連不斷的死亡，熱帶非洲的傳教活動再次陷入低潮的時刻：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年的旅行中，整個非洲的歷史軌道都將有所改變。