Mulenga fixo varias aparicións para a selección de fútbol de Zambia e participou no campionato de 1990.
e a final da Copa Africana de Nacións de 1992. Tamén xogou para Zambia nos Xogos Olímpicos de 1988 en Seúl.