Вскоре после этого доклада члены Географического общества организовали новую экспедицию в Африку. Начальной целью экспедиции было: «1. Проникнуть в область махдистов, недоступную уже несколько лет европейцам для изучения движения в Судане. 2. Попутное, по возможности всестороннее исследование Абиссинии». Экспедицию возглавил офицер Николай Степанович Леонтьев. Участниками ее были географ и врач A.B. Елисеев и отставной офицер К. С. Звягин. Перед отъездом в Африку, 12 ноября 1894 г., Елисеев написал в совет общества большое письмо: «Отправляясь в новое путешествие под авторитетным покровительством Русского географического общества, ввиду сложности задач, возложенных на меня нашей экспедицией, я никак не мог определить в точности времени, потребного для свершения путешествия в задуманных размерах. Зарабатывая себе хлеб тяжелым повседневным трудом и состоя на государственной службе без содержания, я при всех моих усилиях в последнее время никак не мог заработать столько, чтобы обеспечить свой дом и семью на время всего путешествия, срока которого определить невозможно. Ввиду того что мои товарищи по путешествию не особенно стеснены материальными средствами, предполагают пробыть в Африке 1 и даже 1,5 года, что было бы весьма желательно для целей нашей поездки, то я нахожусь в весьма затруднительном положении. Обеспечив свою семью всего на 8 месяцев, я должен по необходимости по истечении этого срока вернуться в Россию, даже оставив своих товарищей в Африке, потому что в противном случае в доме не осталось бы уже ни одной копейки.
Ввиду таких обстоятельств я осмеливаюсь обратиться с покорнейшей просьбой к совету общества, который, быть может, найдет возможным тем или другим способом поддержать мой дом по истечении 8 месяцев, если наша поездка продолжится более этого срока. Такая помощь сняла бы окончательно мои неизбежные заботы о будущем своих близких и позволила бы остаться в Африке столько времени, сколько потребовали бы задачи, поставленные нашей экспедицией. Субсидия в сто рублей ежемесячно начиная с 15 августа 1895 г. была бы вполне достаточной для обеспечения моего дома. Субсидия эта могла бы быть выдаваема г. секретарем общества одному из лиц, близких мне и известных лично A.B. Григорьеву».
Нельзя без волнения читать письмо Елисеева, написанное за полгода до его смерти, накануне экспедиции в Эфиопию, которая стала для него последней. В январе 1895 г. экспедиция прибыла в Обок и далее направилась в Джибути и Харар, где произошла встреча русских путешественников с Расом Маконеном и Менеликом. Русским был оказан такой горячий прием, что Леонтьев вынужден был направить Елисеева в Петербург для переговоров об отправлении в Россию из Эфиопии первой дипломатической миссии. 12 февраля 1895 г. Елисеев выехал из Харара, захватив с собой коллекции, собранные экспедицией в феврале 1895 г.
В начале мая Елисеев приехал в Петербург. 10 мая он выступил на общем собрании Географического общества с докладом о путешествии в Эфиопию, уже тогда он был болен дифтеритом. 22 мая A.B. Елисеев скончался в возрасте 37 лет. Леонтьев и Звягин вернулись на родину вместе с первой эфиопской дипломатической миссией.
За большие научные труды и содействие в установлении дружественных связей между Россией и Эфиопией все расходы этой экспедиции русское правительство приняло на свой счет.
В январе 1896 г. Леонтьев вновь отправился в Эфиопию, где вскоре стал военным советником негуса во время итало-эфиопской войны 1895–1896 гг. В сентябре 1897 г. он вернулся в Петербург вместе с эфиопской миссией и после короткого пребывания на родине вновь отправился в Эфиопию, где был принят негусом на постоянную службу. В 1898 г. Леонтьев был назначен правителем Экваториальных провинций Эфиопии. Экспедиция под его руководством исследовала огромную территорию по р. Омо и оз. Рудольф.
Последние годы жизни Леонтьев провел в Париже, где и скончался 17 июня 1910 г. «Питая глубокое уважение к Русскому географическому обществу, высоко ценя и любя его деятельность и считая себя как бы обязанным обществу за свои первые успехи, в особенности первые годы своих путешествий в Абиссинии», Леонтьев еще в 1908 г. составил завещание в пользу Географического общества.