Mutumba started his career in Vasalunds IF as a young child, but in 1999 he joined AIK, still as a youth player. In the fall of 2002 he made his first appearance with the senior squad against Kalmar FF, playing the last five minutes of the game. In 2004 AIK wanted Mutumba to play with FC Café Opera, a club that AIK had a close relationship with and later would become their feeder club. Unfortunately, Mutumba broke his leg in an indoor tournament he played with some friends before the season had started and he was never able to play any matches for Café Opera. He stated that he lost his interest in football and "started hanging with the wrong crowd". This eventually landed him with a battery and assault charge. A judicial court gave him a second chance and he decided to continue with football.
When the Finnish season ended in the fall of 2007 Mutumba tried out for Spanish La Liga club Deportivo de La Coruña, his old club AIK and Scottish Premier League club Hibernian. Mutumba himself reported that he turned down a deal from Deportivo La Coruña, and British media claimed he signed a short-term contract with Hibernian. In a 2009 interview with Swedish newspaper Aftonbladet he stated that the deal with Deportivo La Coruña fell through due to problems on behalf of his agent, and he explained that they were talking about the development team, Fabril, who play in the Spanish Segunda B division. In the end he signed with Superettan club FC Väsby United, where he had previously been under contract in 2004 when the club was still known as "FC Café Opera“.
AIK (second spell)
In November 2008 he signed with AIK again. Following his return to the club, he stated that he was where he wanted to be and that it was highly unlikely that he would move abroad again and that the money offered to him was not going to be decisive. In the last game of the 2009 season AIK beat IFK Göteborg 2–1 in a dramatic title-deciding match, claiming the Allsvenskan championship for the first time in eleven years. In the match 55th minute, Mutumba provided the assist to his teammate Antônio Flávio, who took the "skillful" feed and rifled the equalizer past IFK Gothenburg's goalkeeper. 2 days before the final game, Mutumba tattooed in "AIK GULD 2LAX9 on his chest. AIK came off to a bad start in the 2010 season, performing badly despite being crowned champions only a few months earlier. The club was nearing a relegation battle due to these bad showings. Manager Mikael Stahre left for Panionios GSS and the team came under heavy criticism for its poor performances.
Videoton
On 28 June 2010, media reported that the Hungarian club of Videoton FC had bought both Bojan Djordjic and Martin Mutumba. The director of the Hungarian club compared Djordjic to Roberto Baggio and Mutumba to Ronaldinho. The transfer led to many speculations in media, especially since AIK had appointed the Scottish manager Alex Miller only a couple of days before the transfer were made. The players claimed that it was Mr. Miller’s decision to let the players go, but the organization of AIK claimed that they got such a good offer that they couldn’t refuse to sell.
AIK (third spell)
In 2011, Mutumba was signed by AIK for the third time, agreeing on a three-year deal with the club. Mutumba's AIK squad number has varied from time to time. During the 2009 season, he wore number 19. When the 2010 season started, he received the number 10 jersey. However, from 2011 to present, he has worn the number 9 jersey. Mutumba's style of playing is mildly skillful and dribbling skills slightly trumps those of the average Allsvenskan player, as was seen when Mutumba was dribbling mediocrately with the Gefle defense, which saw AIK winning 3-0.
Çaykur Rizespor
On 5 January 2014, Çaykur Rizespor announced that Mutumba signed with them for 2.5 years.
When he originally signed on with AIK, still a teenager, his father quit his job and the young Mutumba provided the family with the only income they had. When the club let him go, the family quickly found themselves in economic hardship. In 2003, Mutumba collaborated on the book "Svartskallar – Så funkar vi" where 11 young people from multicultural and minority backgrounds talk about what it is like to be of immigrant background in modern Swedish society. Mutumba loves music and is a huge fan of reggae, rap music and samba. A keen rapper, he has released tracks under the moniker M9. He has a tattoo on his left temple that says "R-BY", a tribute to Rinkeby, the suburb in Stockholm where he grew up and still resides. Days before the deciding final game of the 2009 season he tattooed "A.I.K GULD 2LAX9" across his chest. Fortunately for him it came true. He is second cousin with former footballer Moses Nsubuga who played for IF Elfsborg and lost his left leg in a car accident 1997. In January 2012, Mutumba got a Ugandan passport and was summoned in the Uganda national team squad that faced Congo Brazzaville in the Africa Cup of Nations qualifiers. However, he didn't play spending all the 90 minutes on bench. Later in June that year, Mutumba made his debut in the Uganda national team that played an away World Cup qualifier with Angola on 3 June 2012.
