W tej wyprawie sprawdził się system skautowy. Dzięki temu, iż wódz został odnaleziony i pojmany bez rozlewu krwi, Baden-Powell został awansowany na majora. W 1890 wraz z wujem udał się na Maltę, a stamtąd do Europy, gdzie został brytyjskim szpiegiem.
Trzy lata później, na własny wniosek został zwolniony ze służby i przeniesiony z powrotem do Afryki. Tam zostało mu przydzielone zadanie aresztowania Prempeha, wodza plemienia Aszanti. W 1896 udało mu się otoczyć Prempeha i wziąć do niewoli. Za ten wyczyn otrzymał awans na pułkownika, zaś Prempeh kilkanaście lat później został założycielem i przewodniczącym organizacji młodych skautów w Ghanie.
Następnie wyjechał do Bulawayo w górach Matopa. Podczas walk w górach Matabele członkowie plemienia, z którym walczył, nadali mu przydomek „Impeesa” co znaczy wilk, który nigdy nie śpi.
W 1896 Baden-Powell został oskarżony o nielegalne wydanie wyroku śmierci na szefa plemienia Matabele, Uwini. Obiecano mu, że jego życie będzie oszczędzone, jeżeli się podda.