Se menestys, joka oli seurannut Livingstonea ja hänen seuralaisiansa matkalla Loandaan, innostutti Makololoja auttamaan häntä itäänkin päin matkustamaan. Ruhtinas Sekeletu lähti Livingstonea seuraamaan 200 miehellä ja antoi hänelle joukon tavaroita, joilla hän saisi vaihettaa itselleen venheitä ja muita tarpeita. Sitäpaitse lupasi Sekeletu Livingstonelle kaiken elefantin-luun, joka vaan löytyi hänen maassaan, ja vaati, että Livingstone ottaisi sitä mukaansa niin paljon kuin hän suinkin taitaisi. Hän sai myös suuren joukon kantajia tavaroita kuljettamaan.
Muutaman päivän kuluttua tuli Livingstone Sambesi-virran suurimman kosken, Viktoria-kosken niskalle, josta lähtien hänen täytyi jatkaa matkaa maata myöten, sillä mahdoton oli enää kulkea veneillä virtaa myöten joka oli muuttunut pauhaavaksi koskeksi, ja syöksi jyrkkäin terävien kallioiden välitse. Viktoria-koskesta kertoo Livingstone, että neekerit sitä sanovat "kaikuvaksi savuksi", ja syynä tähän on, että siitä nousee tavattoman suuria höyrypatsaita, joiden huiput ylettyvät pilviin asti. Alapäästä ovat nuo höyrypatsaat vaaleita, vaan ylhäältä tummat, joten ne ovatkin hyvin savun näköisiä. Sambesi-virta syöksee täältä äkkijyrkästi syvään kallioiden väliseen kuiluun, joka on niin kapea, ettei virran niskalla venheellä kulkija ollenkaan näe mihin tuo ääretön vedenpaljous katoaa. Kosken suuruuden voi arvata kun ajattelee, että se tuhannen kyynärän levyisenä syöksee jyrkän kallion yli suoraan 310 jalkaa alas ja sitte ahdistuu kallionrotkoon, joka ei ole leveämpi kuin 40 kyynärää. Koskesta nouseva höyry taajenee ylempänä ilmassa ja putoaa takaisin maahan lakkaamattomana sateena. Vähäiseen saareen kosken niskalla kylvi Livingstone monenlaisia siemeniä, ollen vakuutettu, että koskesta nouseva höyry ja kosteus auttaisi hänen istutuksiaan kasvamaan.
Sekeletu oli saattanut Livingstonea Batokain maahan, jotka ennen ovat olleet itsenäiset ja harjoittivat silloin suurimpia julmuuksia ja ilkitöitä, kunnes Sekeletun isä Sebituane pakoitti osan heistä alamaisiksensa. Maa, jonka kautta Livingstone kulki, oli erittäin kaunista ja oli ennen ollut tiheästi asuttua, mutta nyt siitä olivat asukkaat vähentyneet hyvin suuressa määrässä edellisten sotien vuoksi. Batokat, jotka olivat äärettömän suurien karjalaumojen omistajat, olivat turhaan koettaneet vastustaa Makololojen valloituspuuhia ja kun he olivat voitetut, olivat Makololot saaneet niin paljon karjaa, etteivät voineet niitä edes pitää luvussa. Sekeletu jätti Livingstonen seuraajiksi 114 miestä saattamaan häntä meren rannalle.
Vähitellen alkoi maa kohota kunnes Livingstone tuli siihen ylämaahan, joka rajoittaa Sisä-Afrikan tasangot ja jonka Sambesi-virta Viktoria-koskessa katkaisee. Tätä seutua Livingstone kuvaa erittäin sopivaksi uudis-asukkaille sen vuoksi, että se on terveellinen ja hedelmällinen. Makololot kehuvat sitä parhaimmaksi maaksi, kuin he tuntevat. Täällä olikin Sekeletun isävainaja Sebituane ensin asunut ennenkun Matebelet hänen sieltä karkoittivat ja ryöstivät häneltä kaiken karjan, jonka jälkeen hän muutti länteen päin ja perusti sen valtakunnan, jossa hänen poikansa nyt hallitsi. Asukkaat olivat vierasvaraisia ja ystävällisiä eivätkä tunteneet orjakauppaa. Metsä-eläviä oli niin paljon, että Livingstone ei sano missään nähneensä sellaista runsautta, mutta kun ne olivat arkoja, oli hänellä kuitenkin vaikeuksiakin saada elätetyksi suurta seuraajajoukkoansa. Monet hänen seuralaisistansa olivat kuitenkin taitavia metsästäjiä ja hankkivat silloin tällöin elefantin tahi jonkun muun suuren elävän paistiksi. Kerran sattui sellaisessa tilaisuudessa, että yöllä heidän ympärillensä kokoutui hyenaparvi, joka ilkeällä ulvomisellaan piti heidät valveilla. Livingstone, joka tiesi että neekerit uskovat hyenain aina tarkoittavan jotakin ulvomisellaan, kysyi väeltänsä syytä siihen, miksi hyenat niin kovasti ulvoivat ja sai vastaukseksi, että ne iloitsevat edeltäpäin siitä saaliista, jonka ne tietävät huomenna saavansa elefantin jäännöksistä.
Lintujakin kertoo Livingstone täällä olevan hyvin suuressa määrässä ja mainitsee niistä omituisen sarvikuonolinnun, jolla nokan päällä on suuri luinen kasvannainen. Kun tämä lintu on tehnyt pesänsä, tavallisesti ontevaan puuhun, ja muninut munansa, niin koiraslintu tukkeaa pesän suun niin pieneksi, että auki jää ainoastaan pieni reikä, josta naaras pistää nokkansa ulos; koiras syöttää naarasta niin kauan, kunnes pojat kykenevät lentoon, jolloin naaras on erinomaisen lihava, ja asukkaat pyytävät sitä silloin suurena herkkupalana; koiras itse on samalla ajalla laihtunut hyvin laihaksi. — Toinen omituinen lintu on mesikäki, joka on hyvin ahnas mettä syömään, mutta kun mehiläispesä sattuu olemaan sellaisessa paikassa, ettei se sitä saavuta, houkuttelee se ihmisiä pesän luo, ja saapi tavallisesti aina osan medestä, kun nämä sen löytävät.
Asukkaat näillä seuduilla ovat hengellisessä kehkeymisessä paljon jäljempänä sisämaan asukkaita, ja olivat silloin kun Livingstone heidän maansa kautta kulki, niin paljon sorretut mahtavampain naapurien hyökkäyksien kautta, että he suurimmalla hartaudella toivoivat rauhaa. He ovat iholtansa vaaleampia, melkein kahvin-värisiä, johon on kaadettu kermaa, eivätkä pidä mustaihoisuutta minäkään kauneutena. He rumentavat itsensä siten, että yleisesti lyövät pois etuhampaat yläleuasta, eikä heidän tirannihallitsijansakaan ole saaneet tätä tapaa poistetuksi.
Orjakaupan ja portukalilaisten kauppiaitten menettelyn seuraukset alkoivat tuntua yhä selvemmin kuta etemmäksi matkustajat kulkivat itään päin. Asukkaat tulivat yhä enemmin vihamielisiksi ja epäluuloisiksi ja usein oli heidän ja matkustajain välillä syttynyt riitoja, jotka olivat vaikeita sovittaa. Kuljettuansa erään Tsumbo-nimisen Portukalilaisten hyljätyn kauppa-aseman jäännöksien ohitse, joutui Livingstone seuralaisineen Portukalilaisten ja alkuasukkaiden sotatantereelle. Hänen täytyi nyt kulkea virran eteläpuolelle, ja jatkaa matkaansa sillä puolella virtaa kunnes hän tuli Tete-nimiseen Portukalilaisten perustamaan kauppapaikkaan, maaliskuulla 1856. Täällä asuva portukalilainen päällikkö Tito Augusto d'Arajo Sicard vastaanotti Livingstonen ystävällisimmällä tavalla. Kun Livingstone maaliskuun 2 p. iltapuolella väsyneenä seisattui Teten ulkopuolella noin 8 engl. peninkulman matkan päähän eikä samana päivänä enää jatkanut matkaa kaupunkiin, vaan jäi yöksi lepäämään leiripaikalle, lähetti hän vaan kaupungin päällysmiehelle ne suosituskirjeet, jotka hän oli saanut Loandan piispalta sekä muilta henkilöiltä siellä. Seuraavana aamuna k:lo 2 heräsi hän kun kaksi upseria sotamieskomppanian kanssa tuli häntä vastaanottamaan tervehtien häntä tervetulleeksi ja tuoden hänelle aineksia eurooppalaisen aamiaisen valmistusta varten. Hänen seuralaisensa hämmästyivät suuresti ja luulivat noiden aseellisten miesten tulleen heitä ja Livingstonea vangitsemaan. Kun Livingstone oli tullut Teteen, sai hän vielä suuremmassa määrässä kokea portukalilaisen päällikön ystävyyttä; sillä tämä koki kaikin tavoin virkistää hänen uupuneita voimiansa, antoi Makololoille maakappaleen viljeltäväksi kunnes he voisivat palata kotiansa, vieläpä piti heitä talossaan kunnes he ennättivät rakentaa itselleen majoja, antoi heille viljaa, y.m. Livingstonen pikku tyttärelle vietäväksi hän lahjoitti rukousnauhan, jonka eräs Teten asukkaista oli valmistanut siellä saadusta kullasta; samoin hän antoi näytteitä kultahiekasta, jota oli saatu kolmesta eri paikasta Teten ympäristöllä ja jotka vieläkin säilytetään geoloogisessa museumissa Lontoossa.
Tetessä Livingstone viipyi puolitoista kuukautta, sillä hänen täytyi odottaa sopivampaa vuodenaikaa matkustaaksensa, ja tutki sillävälin tarkemmin näitä seutuja. Tetessä ovat Portukalilaiset hallinneet jo kauan aikaa, ainakin toista sataa vuotta, vaan kuitenkaan ei tämä uudisasuntola ole voinut kehittyä parempaan kukoistukseen, vaikka se on luonnostansa rikkaalla ja hyvin edullisella paikalla. Suurin syy siihen on orjakauppa ja Portukalilaisten sodat alkuasukasten kanssa. Kerran oli sellaisen sodan ajalta Teten maaherra lähtenyt kurittamaan erästä kapinoitsijaa, mutta tämä oli lähettänyt joukon väestänsä Teteen, ja turvattomana tuli silloin kaupunki perin pohjin hävitetyksi tulipalon kautta, niin ettei jäänyt kuin kirkko jäljelle. Livingstonen aikana oli kaupungissa vieläkin jäännöksiä ja raunioita näiltä ajoilta, ja Teten koko asukasluku oli parin tuhannen paikoilla. Kahvin sekä muiden hyödyllisten kasvien viljelys on joutunut suuresti rappiolle entisiin aikoihin verraten. Paitse kultaa, jota täällä on huuhtomalla löydetty, on myös runsaassa määrässä rautaa, joka on erinomaisen hyvää. Kasvikunnan rikkaudesta voisi toimelijaisuudella saada hyvinkin suurta hyötyä tälle maalle, mutta valitettavasti on kauppa kulkenut monen käden kautta eikä suoranaista yhteyttä ole pidetty emämaan ja siirtokuntien välillä. Suurin onnettomuus maalle on kuitenkin orjakauppa, joka tuskin meidänkään aikoinamme lienee lakannut näillä seuduilla.
Saatuansa tietää, että Sambesi-virran suupuolella oli tullut nälkä-aika, päätti Livingstone jättää seuralaisensa Makololot Teteen ja jatkaa matkaansa ainoastaan muutamain toverien kanssa. Välttääksensä epäluuloa, jätti hän kaiken Sekeletun hänelle antaman elefantin-luun erään luotettavan Portukalilaisen haltuun sillä käskyllä, että jos hän ei palajaisikaan, tämä möisi sen ja lähettäisi sen edestä tavaroita Sekeletulle. Muutoin oli Livingstonen tarkoitus lähteä Englantiin niin pian kun hänelle siihen ilmestyisi tilaisuus, sekä palata sieltä jonkun ajan kuluttua. Englannissa hän tuumi ostaa omilla varoillansa tavaroita Sekeletulle, ja sitte ottaa palkinnokseen niiden hinnan siitä summasta, joka saataisiin kun elefantin-luu olisi saatu myydyksi.
Lähdettyänsä Tetestä huhtikuun 22 p:nä v. 1856 kulki Livingstone veneillä pitkin Sambesi-virtaa Senna nimisen, rappiolle joutuneen portukalilaisen kylän ohitse, jonka asukkaat hänelle kuitenkin osoittivat kaikkea ystävyyttä. Virta on täällä ala-varrellansa jo paisunut niin suureksi, että kun Livingstone oli keskellä virtaa, niin ei kumpaakaan rantaa näkynyt. Vasemmalla puolella laskee siihen likellä sen suuta Shire niminen lisävirta, joka kulkee erittäin hedelmällisten ja terveellisten seutujen halki, jotka sen pahempi, ovat jääneet sivistymättömien neekerien haltuun, vaikka kyllä alku olikin tehty näiden maiden viljelemiseen ja niiden asukkaiden sivistyttämiseen.