Stanley je zavrnil kar nekaj Leopoldovih prošenj, nato pa ga je ta ujel na limanice, češ da bo pač poslal nekoga drugega. Stanley, ki se nikoli ni branil denarja in slave, je leta 1878, pet mesecev po tem, ko se je bil vrnil iz Afrike, vendarle privolil. Podpisal je petletno pogodbo, po kateri bi za leto, prebito v Evropi, prejel petindvajset tisoč frankov, za leto v Afriki pa petdeset tisoč frankov (približno 250 tisoč današnjih dolarjev). Seveda je celotno akcijo vodil in financiral Leopold II. Pogodba je določala, da bo Stanley najprej v iztoku reke zgradil bazo, na območjih brzic pa cesto, po kateri bodo nosači prenašali razstavljene dele parnikov do naslednjega plovnega rečnega odseka. Stanley je moral za vnaprejšnje izplačilo obljubljene vsote podpisati vrsto pogodb, zanimivo pri tem pa je, da ni povsem jasno vedel, za koga dela: za kralja, za Leopoldovo Mednarodno afriško združenje ali za novi skrivnostni Komite za študije zgornjega Konga. Kakorkoli, z denarjem v žepu se ni več obremenjeval z njegovim izvorom, temveč je z izplutjem iz pristanišča februarja 1879 začel uresničevati pogodbo. Pet let je ostal na črni celini. Kmalu so celotno zaledje reke poimenovali Kongo. Njegovo delovanje je bilo osredotočeno na neusmiljen teren, odet v nepregledno zelenje džungle. Po dveh letih zemeljskih del in gradnje novih objektov sta iz novozgrajene baze izplula po reki navzgor dva majhna parnika z delavci, ki naj bi na bregu postavili še več baz. Imena teh niso dopuščala nobenega dvoma o tem, čigava je kolonija: glavna baza se je imenovala Leopoldville, gričevje nad njo Leopoldov hrib, kmalu sta se na zemljevidu znašla tudi Leopoldovo jezero in Leopoldova reka. Videč, da delo poteka nemoteno, si je kralj Leopold II. želel čim več Konga – in to čim hitreje! Njegova pisma Stanleyju jasno kažejo njegovo lakoto po novih ozemljih: »Nujno morate zaseči čim več zemlje in jo nemudoma podvreči vrhovnemu gospostvu. Niti minute ne smete izgubiti!« Leopold se je zavedal, da mora prehiteti druge kolonialne sile, ki so že stegovale roke proti Kongu. Francozi so tako z enim od domorodnih plemen na severnem obrežju Stanleyjevega bazena sklenili dogovor o pravici do uporabe brega, Portugalci pa so s podporo Britancev zahtevali ustje reke Kongo. Stanley je zato prestavil v višjo prestavo in še bolj gnal delavce, Leopold pa je s pomočjo oxfordskih pravnikov sestavil pogodbo, ki bi jo Stanley pomolil pod nos domorodnim