Livingstone matkusti ensin Bombaihin Intiassa, jossa hän otti mukaansa muutamia nuoria neekereitä, joita siellä lähetyskoulussa kasvatettiin lähetyssaarnaajiksi, sekä kaksitoista intialaista sotamiestä hoitamaan niitä aaseja ja kameleja, jotka hän oli matkaansa varten hankkinut, sillä nämä eivät kuole tsetse-kärpäsen puremasta niinkuin raavaseläimet ja hevoset. Tultuansa Afrikaan hankki Livingstone palvelukseensa myöskin muutamia miehiä Antsuan- eli Johanna-saarelta Mosambik-kanavassa, sillä tämän saaren asukkaita pidetään luotettavina ja kelvollisina tavarankantajina. Hänellä oli siis mukanansa kohtalaisen suuri seurue, jossa oli 12 intialaista sotamiestä, 9 miestä Johanna-saarelta, 1 Komoro-saaristolainen, 7 vapautettua orjaa ja 2 miestä Sambesin varrelta, jotka hän oli ottanut mukaansa koetteeksi. Eläimiä hänellä oli kuusi kamelia, kolme puhvelia, kaksi muulia ja kolme aasia, yhteensä 31 miestä, joista nuo intialaiset sotamiehet olivat varustetut kelvollisilla Enfield-mallin mukaan tehdyillä rihlatuilla kivääreillä. Livingstone oli nämä aseet saanut lahjaksi Intian hallitukselta. Kun raha noissa tuntemattomissa maissa oli aivan arvotonta, sillä maan asukkaat eivät sille antaneet mitään arvoa, vaan tekivät vaihtokauppaa, niin täytyi Livingstonen viedä mukanansa kymmenen pakkaa vaatetta ja kaksi säkillistä lasihelmiä, joilla hän voisi vaihettaa tarpeita alkuasukkailta. Sitäpaitse oli hänellä omaa tarvistansa varten monta laatikkoa lääkkeitä, vaatteita, tieteellisiä koneita ja muita tarpeellisia tavaroita. Livingstone alkoi matkansa Rovuma-virran vasenta rantaa kulkien ja tällä matkalla häntä kohtasi ylen paljo hankaluuksia. Usein hänen täytyi kirveillä hakkuuttaa auki tie edestänsä kun se oli niin kapea, ettei sitä käynyt kulkeminen. Näillä pienillä poluilla, jotka mutkittelivat aivan sinne tänne tiheässä metsässä, oli kamelien vaikea kulkea, sillä niiden korkeus teki, että puiden oksat heitä estivät. Matkan hankaluutta ja hitautta lisäsi vielä Johanna-miesten ja intialaisten haluttomuus jo velttous työnteossa.

Jo matkan alussa olivat sipojit (siksi nimitetään syntyänsä intialaista sotaväkeä) sekä Johanna-saarelaiset kyllästyneet eteenpäin kulkemiseen ja kokivat siten pakoittaa Livingstonea palajamaan takaisin, että he rääkkäsivät juhdat kuoliaiksi. Kun ei tämä koe auttanut, yllyttivät he alkuasukkaita Livingstonea vastaan syytellen häntä kaikella tavoin. Livingstone tuskautui tällaisista kujeista ja erotti sipojit pois seurastansa. Hän antoi heidän palata takaisin rantamaalle ja varusti heille kylliksi tarpeita paluumatkalle. Nuo sipojit olivat niin ilkeätä joukkoa, että alkuasukkaat luulivat heitä Livingstonen orjiksi. Heillä oli tapana pakoittaa ensimmäistä lasta tahi vaimoa, jonka tapasivat, kantamaan heidän pyssyjänsä ja ampumavarojansa, ja käyttivät neekeriä vastaan uhkauksia ja lupauksia, joita eivät kuitenkaan voineet täyttää. Tunnin marssiminen oli kylliksi riittävä aika että he jo valittivat uupumusta; he olivat silloin jo olevinansa aivan voimattomia ja seisattuivat viivytellen siten kulkua, ja miettivät uusia juonia isäntäänsä vastaan. Selvää on, ettei tällaisista puolustajoista olisi ollut muuta kuin vastusta jos joku suurempi vihollisparvi olisi Livingstonea ahdistanut.

Rovuma-laaksossa oli tullut nälkä-aika, ja vaikka asukkaat vastaanottivat Livingstonen ystävällisesti, niin oli hänen kuitenkin ollut vaikea saada seurueellensa kylliksi ruoka-aineita. Hän oli kuitenkin päässyt Rovuma-virran lähteiden ohitse kesäkuussa 1866 erääsen kylään, jonka hallitsija oli Uhijou-nimiseen kansaan kuuluva päällikkö. Tämä kylä oli kahdeksan päivänmatkaa Rovuma-virran eteläpuolella ja siitä oli lavea näköala Niassa-järven ja siihen laskevien jokien ja virtojen yli. Tämän paikan ja Rovuman välinen seutu oli asumatonta erämaata, jossa Livingstonen seurue oli kärsinyt paljon nälkää ja moni hänen miehistänsä oli karannut.

Livingstone saapui elokuussa 1866 Mponda nimisen päällikön kylään, jonka alue on Niassa-järven läheisyydessä. Tällä matkalla karkasi häneltä taas pari miestä, ja eräs kolmas, nimeltä Bekotani, jota Livingstone oli suuresti suosinut, tahtoi myös erota, sanoen syyksi, että hän oli tavannut veljensä, joka muka asui Niassa-järven itäpuolella ja että hänen sisarensa oli Mpondan lempi-vaimo. Kun Livingstone huomasi Bekotanin haluttomuuden seurata häntä, vei hän tämän Mpondan luo, ja siellä tuli ilmi, että Bekotani oli puhunut valhetta. Livingstone jätti tuon vastahakoisen seuralaisen Mpondan luo — saatuansa kuitenkin ensin vakuutuksen, ettei häntä pahoin kohdeltaisi — varusti hänet vaatteilla ja helmillä, kunnes hänen "suuri veljensä" tulisi häntä vastaanottamaan. Tämä hyväntahtoisuus Livingstonen puolelta sai kuitenkin huonon palkan. Bekotani koki kaikin tavoin houkutella entistä toveriansa, erästä toista Livingstonen palvelijaa, nimeltä Chumah luopumaan Livingstonen luota ja jäämään hänen luoksensa. Hän lupasi veljensä kautta toimittaa Chumah'ille vaimon ja niin paljon olutta juoda kuin vaan haluttaisi. Chumah kysyi kuitenkin neuvoa Livingstonelta, joka häntä kielsi uskomasta Bekotanin viettelyksiä, sillä hän epäili tämän aikovan tehdä entisen toverinsa orjaksi. Chumah olikin kylliksi varovainen ettei luottanut tuohon kavalaan viettelijään, vaan pysyi Livingstonelle uskollisena koko matkalla.

Livingstone aikoi kulkea Niassan yli, mutta arapialaiset, jotka kyllä tiesivät, että Livingstone aina julkisesti vastusti heidän ilkeätä orjakauppaansa, eivät antaneet hänelle lainaksi minkäänlaisia venheitä, vaikka niitä kyllä lupailivat, ja viimein täytyi Livingstonen kulkea järven eteläpuolitse sen ympäri, kun hän kauan oli turhaan odotellut arapialaisten lupauksien täyttämistä.

Niassan rantamaalla tuli eräs arapialainen samaan kylään, missä Livingstone oli ja kertoi että parvi järven länsipuolella asuvaa Masitu-kansaa oli ryöstänyt häneltä kaikki hänen tavaransa. Johanna-saarelaisten päällikkö Musa sai tästä kyllin syytä ruvetaksensa juonittelemaan Livingstonea vastaan. Hän tuli Livingstonen luo kertomaan tuota kuulemaansa juttua, eikä mitkään hirveät sivukohdat siinä suinkaan jääneet unhotuksiin. Livingstone kysyi uskoiko Musa tuota kertomusta.

"Aivan varmaan, sillä tuo arapialainen vakuutti että se on totta, oikein totta".

Livingstone arveli, ettei tuon arapialaisen puhetta ollut uskominen, sillä Masitut eivät olisi tyytyneet pelkkään rosvoamiseen, vaan olisivat hänet tappaneetkin. Saadaksensa asiassa luotettavaa tietoa, mentiin kylän päällikön ajatusta kysymään, ja tämä selitti heti arvelematta arapialaisen puheet perättömiksi valheiksi, sillä jos joku hyökkäys olisi hänen alueellensa tehty, niin hän olisi varmaan saanut siitä tiedon.

Tähän ei kuitenkaan Musa tyytynyt, vaan väitti: "Ei, ei, tohtori, ei, ei, ei! Minä en tahdo tulla Masitujen luo, heidän tapettavakseen. Minä tahdon nähdä jälleen isäni, äitini ja lapseni kotona Johannassa. En tahdo tietääkään mitään koko Masituista!"

Tähän vastasi Livingstone, ettei hänkään tahtonut, että Masitut tappaisivat Musan, vaan koska tämä oli peloissaan, niin hän lupasi kulkea suoraan länteen päin kunnes tulisivat niin kauas, etteivät viholliset heitä saavuttaisi.