Beseda "basenji" v jeziku pigmejcev pomeni "majhna divja stvar iz grmovja". Njihova domovina je Centralna Afrika, kjer so tisocletja živeli, v tesnem stiku z domorodnimi plemeni. Obicajno so živeli kot neodvisno krdelo blizu vasi in, glede na kulturo posameznega plemena, sodelovali z ljudmi. Tudi njihova reprodukcija je na tisoce let potekala brez posebnega vm ešavanja ljudi, zato je pasma ostala zelo izvirna. Domorodci so jih in jih še vedno uporabljajo za pomoc pri lovu.
Tocen cas izvora pasme ni povsem jasen. Najnovejše DNK raziskave so pokazale, da se je najbljižji prednik Basenjija odcepil od skupnega prednika z volkom, 12.100 let nazaj, kar ga uvršca med eno najstarejših pasem psov na svetu. Prvi psi, podobnega tipa, so bili upodobljeni na starih egipcanskih grafikah 3200 - 3000 let p.n.š. Prikazani so kot hišni psi, sedeci ob ali pod stolom svojega gospodarja ter kot spremljevalci na lovu. Prvi psi identicnega videza današnjih Basenjijev, so upodobljeni na nagrobnikih in stenah iz casa Faraonske IV. dinastije, 2613 - 2494 p.n.š. V zapisih poleg slik je ta pes opisan kot pes, ki se premika zelo potiho, nima pasjega vonja in se umiva kot macka. Zaradi teh lastnosti je bil tudi visoko cenjen pri civiliziranih ljudstvih. Pasma Basenji, kot jo poznamo danes pa se je z adaptacijo na življenje v Afriškem pragozdu vzpostavila 4.000 do 2.000 let nazaj.
Od propada egipcanske civilizacije pa do sredine 19. stoletja, so basenjiji zbledeli v popolno pozabo, ceprav je ocitno, da so globoko v centralni Afriki, stran od civilizacije, ostali ohranjeni. V drugi polovici 19.stol. so jih raziskovalci "temnega kontinenta" prvic opazili, kot spremljevalce številnih tamkajšnih plemen. Dobili so tudi razlicna imena: Kongo terier, Bongo, Nyam-Nyam in Zande psi. Prvi uradni uvoz Basenjijev iz Konga v Evropo se je zgodil šele leta 1936, ko so bili v Anglijo pripeljani prve trije predstavniki. Od takrat pa do leta 2013, ko so rodovno knjigo po vsej vrjetnosti dokoncno zaprli za divje predstavnike, so z razlicnimi projekti in odpravami v Evropo in Ameriko skupno pripeljali 60 psov. Kljub zacetnim poginom, so vzreditelji uspeli izboljšati pasmo samo s preživelimi psi ter novimi uvozi in tako križanje z drugimi pasmami nikoli ni bilo potrebno.
Standard mednarodne kinološke zveze FCI za Basenji pasmo, je bil uradno sprejet leta 1964. S tem so Basenjije uvrstili v 5 FCI skupino, kamor sodijo špici in pratipski psi, v oddelek psov primitivnega tipa, brez delovnega izpita.
V Slovenijo so bili prvi Basenjiji pripeljani leta 1998 s Hrvaške, prvo Slovensko leglo pa je bilo vzrejeno dve leti za tem.