Retkikunta lähti Englannista maaliskuussa 1858.
Kap-kaupungissa poikettuaan se seuraavassa toukokuussa saapui Itä-Afrikan rannikolle, jossa se ensi työkseen ryhtyi tutkimaan Sambesin soveliaisuutta kauppatieksi ja samalla siksi tieksi, jota kristinusko vietäisiin Afrikan sisäosiin. Livingstone toivoi tästä vesiväylästä suuria, mutta tarkempi tutkimus osoitti, että hän oli arvannut voitettavat vaikeudet aivan liian pieniksi. Ne alkoivat heti joen suistamossa, joka purkautuvan veden paljoudesta huolimatta ei tarjoa ainoatakaan kunnollista väylää. Suurimmat suuhaarat ovat Milambe, Kongone, Luabo ja Timbwe eli Muselo. Tulvavedellä on koko suistamo rämeenä ja pudassokkelona, joka herkeämättä muuttaa muotoaan sitämukaa kuin virran kuljettama hiekka ja liete rakentavat maata ja vesi jälleen sitä hävittää. Intian meren suolaisen veden kohdatessaan liete vaipuu pohjaan muodostaen suistamouomain poikki vaarallisia hietasärkkiä, »baareja», joiden yli suuret laivat eivät ensinkään pääse jokeen.
Kun Livingstone oli saanut Englannista tuomansa pienen höyryn, »Ma Robertin», kootuksi, lähti hän sillä Kongoneen, suurimpaan ja helpoimmin kuljettavaan suuhaaraan. Retkeilijöitä ihastutti näiden matalain rantain uhkuva mangrove- ja palmukasvullisuus, joka Kirkille tarjosi oivallisen tutkimusalueen. Toisin paikoin oli laajoja niittyjä ja miehenkorkuista heinää. Mutta asukkaita tässä suistamossa oli vähän, koska sotaiset sulut viime aikoina olivat tunkeutuneet Sambesin suistamoon ja sen ylikin, pitäen maan herroja, portugalilaisiakin niin ahtaalla, että heidän täytyi maksaa suluille veroa. Määräaikoina nämä aina saapuivat portugalilaisiin siirtokuntiin kiskomaan veroa portugalilaisilta kauppiailta ja peloittamaan kaikkia hurjilla sotilaskarkeloillaan. Heidän mellastuksensa oli suurena syynä siirtokuntain rappiotilaan. »Ma Robert» oli hirmuinen puunkuluttaja ja koneenkäyttäjä huokaili, kun ei ollut lieteen työntää muuta kuin kallisarvoista ebenpuuta ja elämänpuuta, joista Lontoossa olisi maksettu valtavat hinnat.
Varsinaiselle Sambesille tultuaan Livingstone mielipahakseen näki, ettei hänen laivansa pitänyt puoliaan edes asukkaitten veneille ja että se muutoinkin oli kaikin puolin epätyydyttävä. Se oli rakennettu uudenaikaisesta ohuesta teräslevystä, joka oli niin heikkoa, että vuotoja ilmestyi yhtä mittaa. Syyskuun 8:ntena »Ma Robert» saapui Teteen, jossa makololot suurella ilolla ottivat suojelijansa vastaan ja heidän runoilijansa oikopäätä laati tämän ilotapauksen johdosta laulun. Makololot olivat kotiutuneet Teteen, toiset menneet naimisiinkin, mutta muutamia kymmeniä oli kuollut isoonrokkoon.
Tete, josta nyt tuli kuudeksi vuodeksi Livingstonen toimikeskus, oli sekä pieni että vielä rappeutunutkin kaupunki, asukkaitten luku nousi 4500 henkeen. Portugalilaiset sotamiehet olivat suureksi osaksi entisiä rikoksentekijöitä, jotka täällä olivat menneet neekerityttöjen kanssa naimisiin. Upseerit ja kauppiaat viettivät aikansa juomingeissa, joista orjat säännöllisesti kantoivat heidät kotiin. Musta väestö oli kaikista Afrikan ääristä kokoonhaalittuja orjia, kaikenlainen taikausko oli vallalla ja katolilainen pappi kilpaili sateentekijänä neekerinoidan kanssa. Livingstone pääsi kaupungin portugalilaisten kanssa sangen hyviin väleihin, vaikka he toiselta puolen koettivatkin estellä hänen toimintaansa, ja neekerisoittajat kokoontuivat usein hänen talonsa eteen ilahduttamaan häntä sansan, marimban ja panhuilun sävelillä ikäviin asti.
Kebrabasan koskella.
Ensi työkseen Livingstone päätti nousta Sambesia Kebrabasa-koskelle, tutkiakseen veden matalimmillaan ollessa, voisiko tätä koskea laivalla nousta — kosken yläpuolella oli, kuten hän tiesi, pitkältä kosketonta jokimatkaa. Marraskuun 9:ntenä alkoi Kebrabasan korkea, monikeilainen vuorijono näkyä edessäpäin. Sambesi on murtanut sen läpi ahtaan, jylhän rotkouoman, jossa valtavat paadet matalalla vedellä synnyttävät pyörteitä ja kuohuja. Matalalla vedellä koskea oli mahdoton nousta laivalla, mutta korkealla vedellä kosken sanottiin tasaantuvan sileäksi alamäeksi ja Livingstone luuli, että sitä silloin voisi laivalla nousta. Nykyään tiedetään, ettei tätä koskijaksoa kanavoimatta ole mahdollista voittaa. »Ma Robert» varsinkin oli aivan voimaton, minkä vuoksi Livingstone palasi Teteen.
Sinne päästyään hän viipymättä tilasi Englannin hallitukselta uuden voimallisemman höyryaluksen ja sitä odottaessaan päätti lähteä Shireä, Sambesin viimeistä vasemmanpuolista syrjäjokea tutkimaan noustakseen järveen, josta sen sanottiin alkavan. Portugalilaisille Shire oli tuntematon, sitä kun ei muka päässyt vesikasvien vuoksi veneillä nousemaan. Rantain väestö oli sitä paitsi vihamielistä.
Livingstone Shirellä.
Tammikuussa 1859 »Ma Robert» saapui Shiren suuhun, joka todella olikin täynnään Pistia stratiotesta, Niilin ja monen muun 'Afrikan joen kiusaa. Höyry kuitenkin voitti vastuksen ja ylempänä kasvi kokonaan katosi. Kun retkikunta tuli ensimmäisen kylän kohdalle, osoittivat asukkaat mitä selvimmin sotaisia aikeitaan, uhaten keihäillä ja myrkkynuolillaan, mutta Livingstonen onnistui puheellaan täydelleen muuttaa suuren vihollisjoukon mieli ja hänen sallittiin häiritsemättä nousta jokea edelleen.