Il club venne fondato nel 1935 come Rhokana United per poi assumere successivamente il nome di Nkana Red Devils nel 1981, semplificato poi in Nkana a partire dal 1992. Nel 1964 il club vinse il suo primo torneo, aggiudicandosi la Zambian Challenge Cup.[2]
Nel 1982 si aggiudicò il suo primo campionato zambiano sotto la guida dell'inglese Jeff Butler, che porterà in dote alla squadra anche i tre successivi allori nazionali, con un record di dieci vittorie, dodici pareggi e zero sconfitte.[3] Nel 1990 arrivò in finale della Coppa dei Campioni d'Africa 1990, persa contro gli algerini del JS Kabylie.
