Shitumba began singing in choirs while still in secondary school, joining the Medical Swing Stars Choir after moving to Lusaka to pursue a career as a doctor. He gave up the latter direction, but continued singing as he knocked around, moving from one job to another. He eventually found his way to the Federal Broadcasting Corporation, where he met fellow broadcaster and father of the Zambian music scene, Alick Nkhata. Nkhata took a liking to Shitumba's voice and invited him to join the Alick Nkhata Quartet, teaching Shitumba to play the guitar as well. They recorded together until 1963, when Shitumba returned to broadcasting. He staked an even bigger claim to fame in Zambia by translating the national anthem from English to Bemba.