Nkhotakota fou originalment un grup de llogarets al segle XIX. Vers 1845 s'hi van establir un ''wali'' o ''jumbe'' dedicat al trafictràfic d'esclaus, i vassall del sultà de [[Zanzíbar]]. El primer ''jumbe'' Salim ibn Abd Allah hi va arribar procedent de la ciutat àrab de Tabora avui a [[Tanzània]] i va establir un estat basat en el comerç d'esclaus i de marfil ; al mateix temps Kota Kota, com el van anomenar, fou un centre de difusió de l'islam. El va succeir un altre suahili de nom Mwinyi Mguzo (o Nguzo) que va governar des de vers 1860 a 1876. Al seu darrere va venir Mwinyi Kisutu qualificat com a membre d'una bona família de [[Zanzíbar]]. El explorador i escriptor anglès Henry Bernard Cotterill hi va estar el 1876 i la descriu com una població amb belles mansions quadrades i moltes palmeres. La bandera vermella de Zanzibar estava hissat a la casa del ''jumbe''. Kisutu va col·laborar amb els britànics i quan aquestos van establir el domini a la zona el 1891, tot i ser esclavista cosa a la que els anglesos s'oposaven, els va seguir donant suport fins a la seva mort el 1894. El va succeir el seu fill Mwinyi Kheiri que va pujar al tron el [[8 de setembre]] de [[1894]]; el maig de 1895 fou deposat pels britànics per haver conspirat per rebutjar la seva autoritat.
Fou afectada greument per les inundacions del 2001.
