Преследуя эту цель, Ливингстон выехал 1, июня 1849 года из Колобенга в сопровождении двух друзей, англичан Освелла и Меррея, и нескольких туземцев, которые должны были присматривать за быками и лошадьми. Им предстоял переезд через пустыню Калагари, который Сечеле считал настолько опасным в это время года, что отказался ехать с ними. Хотя Калагари не представляет такой безжизненной пустыни, как Сахара, но к июню она настолько высыхает, что люди и животные с трудом находят для себя воду. Ливингстону и его спутникам пришлось жестоко страдать от недостатка последней. Миражи дразнили путешественников; однажды Освелл и Ливингстон были убеждены, что видят большое озеро, но это было лишь отражение солнечных лучей в высохшем солончаке. 4 июля путешественники приблизились наконец к широкому водному пространству; это была красивая, многоводная река Зуга, о которой туземцы говорили, что она течет из озера. Уверившись, что слухи не обманули его, что он действительно приближается к большому пресноводному озеру, Ливингстон с облегченным сердцем следовал по течению обильной водою реки, на берегах которой была богатая и разнообразная растительность и часто попадались деревни. Еще более широкие перспективы открылись перед ним, когда он дошел до впадения реки Таманакль в Зугу: он убеждался теперь в справедливости сведений, полученных от баквена, бывавших в области, подвластной Себитуане, что Таманакль – одна из многочисленных рек, орошающих эту область. Вместо громадной песчаной и плоской возвышенности, какую ученые предполагали в тех местностях, куда теперь направлялся Ливингстон, там оказывалась обильно орошенная, а следовательно, и плодородная страна. Это открытие наполняло таким восторгом душу Ливингстона, что открытие озера Нгами, к которому он подошел 4 августа, показалось ему уже не столь значительным, каким представлялось прежде. Между тем озеро было громадной водной поверхностью; противоположного берега его нельзя было видеть, и, по показаниям туземцев, нужно было не менее трех дней, чтобы объехать его кругом. Себитуане жил в трехстах верстах к северу от озера, но Ливингстон на этот раз не мог добраться до него. Лечулатебе, вождь племени бакобов, жившего у озера Нгами, желал видеть у себя Ливингстона, но не хотел, чтобы тот ехал к Себитуане: он опасался, что последний приобретет ружья у Ливингстона и его спутников и станет еще сильнее. Поэтому он запретил подвластным ему бакобам оказать Ливингстону необходимую для него помощь при переправе через Зугу. Ливингстон пробовал построить собственными средствами плот для переправы, несмотря на опасность от водившихся здесь во множестве крокодилов; однако работа оказалась ему не по силам, и время года было слишком позднее. Он решился выступить в обратный путь, с тем чтобы в другое время возобновить свою попытку проникнуть к Себитуане.
То, что сделал Ливингстон даже в это первое путешествие, не удавалось еще никому из путешественников по Южной Африке. Лондонское географическое общество, узнав из отчетов Ливингстона миссионерскому обществу о сделанных им открытиях, прислало ему свою благодарность и двадцать пять гиней награды. Это было первое признание научных заслуг Ливингстона и первое оглашение его имени в научном мире.
В апреле следующего 1850 года Ливингстон повторил попытку добраться до Себитуане и выехал из Колобенга в сопровождении Сечеле, Мебальве, двадцати баквена, жены и детей, которых тогда у него было трое. Ему было так тяжело расставаться с семьей, что он решил взять ее с собою несмотря на опасности, какими грозило путешествие по безводным или лихорадочным местностям. Цель путешествия и на этот раз не была достигнута. Путешественников поджидало множество затруднений: по берегам Зуги растительность была чрезвычайно густа, и приходилось вырубать деревья, чтобы очищать дорогу для повозок; на берегах Таманакля оказалась страшная муха цеце, укус которой смертелен для рогатого скота и лошадей. Доехав до озера Нгами, Ливингстон хотел оставить свою семью на попечение Лечулатебе, который уже успел выпросить за то дорогое ружье, но двое детей заболели лихорадкой, и Ливингстон поспешил вернуться домой.
Третье, более удачное путешествие было предпринято им через год, в апреле 1851 года. Он выехал из Колобенга в сопровождении Освелла и семьи, намереваясь перенести свое местопребывание в более здоровую местность, которая, по его предположению, должна была находиться к северу от озера Нгами. Путники ехали прежней дорогой и должны были пересечь Калагари в то время, когда пустыня особенно страдала от засухи. Проводник-бушмен сбился с дороги, и в течение четырех дней путешественники вовсе были лишены воды. Но, вместо того чтобы упрекнуть проводника за неосторожность и выразить опасение за участь детей, Ливингстон, как рассказывает он в своем дневнике, в эти дни сблизился с проводником и всего более сожалел, что такой способный и правдивый народ, как бушмены, лишен света христианской веры.
Дети Ливингстона жестоко страдали от тяжелых переездов и укусов москитов, и он все более и более сознавал невозможность путешествовать вместе с ними; с другой стороны, ни в Колобенге, ни в Курумане нельзя было оставить их с уверенностью за их безопасность ввиду нападений голландских поселенцев (буров), ярых противников английской миссии, препятствовавшей им эксплуатировать местное население. Для Ливингстона представлялся только один исход – отправить семью в Англию в надежде, что со временем она вернется к нему, когда он найдет здоровую и спокойную местность во владениях Себитуане.
На Себитуане Ливингстон возлагал большие надежды. Народная молва прославляла этого могущественного вождя за его мужество и умение покорять людей не только силой, но и добротой. Ливингстону было известно, что Себитуане давно уже желает его видеть и встретит его вполне благосклонно. Приобрести расположение властителя обширной страны было делом весьма важным для успеха миссии; можно было рассчитывать, что в обширных пределах, в которых распространялась власть Себитуане, окажется наконец здоровое и удобное место для миссионерского пункта, какое искал Ливингстон. Прием Себитуане как нельзя более соответствовал его ожиданиям. Он выехал навстречу белым людям (Ливингстону и Освеллу), выказал большую радость при свидании с ними и просил ни о чем не заботиться, так как он доставит им все необходимое. Ливингстон называет Себитуане «бесспорно самым замечательным человеком во всей этой стране»; он был высокого роста и крепкого сложения, со светло-коричневым цветом кожи, и обращение его отличалось достоинством и добродушием, какого Ливингстон не видал ни у одного из африканских властителей. Он подарил гостям несколько быков и кружек меду и несколько выделанных бычачьих шкур, которые должны были заменять одеяла. На другой день после приезда европейцев, еще до рассвета, Себитуане пришел к Ливингстону и Освеллу, уселся у костра и рассказал им свою историю, как он из вождя небольшого племени сделался властителем многих племен, расселенных на обширном пространстве. Себитуане присутствовал на первом богослужении в следующее воскресенье, и Ливингстон искренно радовался, что на его долю выпало возвестить евангельские истины выдающемуся властелину неведомой страны. Себитуане относился к нему с безусловным доверием, и близость их возрастала со дня на день, но скоро наступил неожиданный и ужасный ее конец: Себитуане заболел воспалением легких и умер после двухнедельной болезни. Ливингстон не решился взять на себя его лечение, опасаясь, что неудачный исход болезни может навлечь месть на него самого и на его семью со стороны приближенных и подчиненных Себитуане.
Смерть Себитуане была тяжелым ударом для Ливингстона, который уже надеялся распространить христианское учение в обширной стране, где о нем еще не слыхали. Власть умершего вождя переходила по закону страны к старшей дочери его, Мамочисане, и та дала Ливингстону разрешение объехать все ее владения. Ливингстон и Освелл двинулись в северо-восточном направлении, проехали через город Линьянти, служивший столицей Себитуане, и 3 августа очутились на берегу величественной реки. Эта река, называвшаяся здесь Сешеке, была Замбези, которая в то время была известна лишь в своем нижнем течении. Открытие Ливингстона, указывавшее, что Замбези протекает в этой стране, было величайшей новостью для географов и считается одним из важнейших открытий знаменитого путешественника. На этот раз он не мог осмотреть ни порогов, находящихся выше, ни водопадов, встречающихся ниже того места, где он видел Замбези; убедившись, что берега этой реки, густо поросшие тростником, неудобны для поселения и не защищают от нападений враждебных племен, Ливингстон отказался от мысли устроить здесь миссионерский пункт и решился предпринять обратную поездку в Колобенг.