Si ritiene che i Sukuma e gli altri gruppi Manyamwesi appartengano allo stesso gruppo delle popolazioni bantu dell'Uganda occidentale, da cui si sarebbero separati intorno al XII secolo a.C., spostandosi nell'odierna Tanzania. Non è noto in quale epoca i Sukuma si siano divisi dagli altri Nyamwesi, che sono collocati più a sud; secondo la tradizione orale, i Sukuma migrarono verso nord per sfuggire alle razzie di un altro popolo noto come Mirambo.

Da un punto di vista storico, è noto che a partire dal XVI secolo iniziò a consolidarsi in Usukuma una struttura politica costituita da piccoli regni (chiefdoms). In epoca precoloniale, i Sukuma commerciavano tra l'altro con il regno di Baganda e con gli altri gruppi Manyamwezi (in particolare con la città di Tabora).

Un rapporto di collaborazione particolarmente forte venne stabilito dai Sukuma con i loro vicini Tatoga, a cui fornivano prodotti agricoli in cambio di bestiame e del servigio dei loro rinomati indovini. I rapporti fra le due etnie erano talmente buoni che nella mitologia Sukuma venne elaborata l'idea che i Tatoga avessero guidato i Sukuma nel loro originario esodo verso nord; coerentemente, i capi dei Sukuma vantavano tradizionalmente una discendenza diretta dai Tatoga. Con i Masai, invece, i rapporti erano principalmente ostili, e centrati sulla competizione per il bestiame. Nel XIX secolo, i Sukuma commerciavano anche gli Arabi che controllavano la costa e Zanzibar.

lL primo europeo a entrare in contatto con i Sukuma fu John Hanning Speke durante il suo viaggio verso il Vittoria (1857). David Livingstone giunse in Usukuma negli anni 1870 e in seguito giunsero i missionari anglicani britannici e cattolici francesi. Quando una grave carestia colpì la zona del Lago Vittoria alla fine del XIX secolo, gli anziani sukuma attribuirono questa sventura all'influenza funesta del Cristianesimo.