Mulenga speelde een aantal keer voor het nationale voetbalteam van Zambia en nam deel aan de Wereldkampioenschappen van 1990.
en de finale van de Afrikaanse Natiesbeker in 1992. Hij speelde ook voor Zambia op de Olympische Zomerspelen van 1988 in Seoul.