Karrierebeginn bei B.93

Mtiliga begann seine Karriere in der Jugendmannschaft seines Heimatvereins B.93 Kopenhagen. Bei B.93 entwickelte er sich zu einem der größten Talente des Landes und galt bereits als Jugendspieler als begehrte Transferaktie. 17-jährig debütierte er 1998 als offensiver Mittelfeldspieler für B.93 in der dänischen Superliga. B.93 befand sich im chronischen Abstiegskampf und legte eine eher kampfbetonte Spielweise an den Tag, die einem offensiv agierenden Spieler gelegen kam. Trotzdem gab er innerhalb seiner ersten 13 Profieinsätze einige Talentproben ab. In Folge stieg B.93 als Tabellenletzter aus der Erstklassigkeit ab und benötigte aufgrund einer angespannten finanziellen Situation dringend Transfererlöse. Rohdiamant Mtligia war somit nicht mehr zu halten und erhielt die Freigabe.

In Folge entbrannte vor allem zwischen den beiden niederländischen Großklubs Ajax Amsterdam und Feyenoord Rotterdam ein regelrechter Kampf um die Transferrechte des Spielers. Mtligia entschied sich für Feyenoord, welche für eine Ablösesumme von knapp einer halben Million Euro den Zuschlag bekamen.

Wechsel zu Feyenoord

Feyenoord verlieh ihn daraufhin postwendend auf unbestimmte Zeit an seinen Satellitenklub Excelsior Rotterdam in die Eerste Divisie, wo er für die folgenden viereinhalb Jahre tätig war. Gleich in seiner Debütsaison in den Niederlanden bot er zum Teil herausragende Leistungen und bestätigte mit zehn Toren in 23 Saisonspielen die hohen Erwartungen. Daraufhin kamen die ersten Mutmaßungen auf, Feyenoord würde das Talent bereits vorzeitig in seinen Kader aufnehmen, was jedoch aufgrund taktischer Überlegungen von Trainer Bert van Marwijk, der ein System ohne offensiven Mittelfeldspieler bevorzugte, nicht zustande kam.

In der Folgespielzeit steigerte sich Mtligia kontinuierlich weiter und feierte mit der Mannschaft den Vizemeistertitel in der Eerste Divisie. In den Play-off-Spielen um den Aufstieg unterlag man jedoch und verblieb in der zweiten Spielklasse. 2001/02 verteidigte man den Vizemeistertitel und stieg in die Eredivisie auf.

Excelsior ging in Folge naturgemäß mit einer ausschließlich aus Talenten wie Gill Swerts, Brett Holman, Mounir El Hamdaoui oder Michel Bastos bestehenden Mannschaft in die Spielzeit, die es schwer hatte, im kampfbetonten Abstiegskampf zu bestehen. Mtligia absolvierte seine erste volle Erstligasaison ohne zu glänzen und wurde eher als Enttäuschung angesehen. Excelsior stieg als Vorletzter wieder in die zweite Spielklasse ab.

In der Spielzeit 2003/04 spielte er daraufhin erstmals auch auf der linken Außenbahn, da er bei Feyenoord als offensiver Freigeist eher geringfügige Einsatzchancen sah. Auch auf links entwickelte er sich zu einem der Leistungsträger der Mannschaft, die abermals zum Saisonende punktegleich mit Meister FC Den Bosch den Vizemeistertitel einfuhr. Mtligia war zu diesem Zeitpunkt bereits im Kader Feyenoords, da van Marwijk ihn bereits im Winter aufgrund einer Verletzungsmisere zum Stammverein zurückholte. In der Rückrunde kam er daraufhin elf Mal zum Einsatz, ohne sich jedoch einen Stammplatz erkämpfen zu können.

Verletzungspech

Zur Spielzeit 2004/05 war er erstmals in der gesamten Saisonvorbereitung von Feyenoord im Kader und wurde als aussichtsreicher Kandidat für den Platz auf der linken Außenbahn gehandelt. Dies hatte vor allem mit der Ausbootung von Routinier Ramon van Haaren zu tun, der während der Vorbereitung an Sparta Rotterdam verliehen wurde. Der frischbestellte Feyenoord-Trainer Ruud Gullit entschied sich jedoch überraschend für den Portugiesen Bruno Basto und gab noch dazu den eigentlich als Innenverteidiger geholten Cory Gibbs auf der linken Seite den Vorzug. Mtiliga kam über die Saison auf lediglich elf Ligaeinsätze ohne Torerfolg und verletzte sich obendrein noch schwer, woraufhin er die gesamte Spielzeit 2005/06 rekonvaleszent war und kein einziges Spiel absolvieren konnte.

Während seines verletzungsbedingten Ausfalls entschied sich der neubestellte Feyenoord-Trainer Erwin Koeman gegen eine Verlängerung seines auslaufenden Vertrags, woraufhin er nach einem Jahr ohne Spielpraxis keinem Verein mehr angehörte.

Neuanfang in Breda

In der Folge kam er bei Ligakonkurrent NAC Breda mit Trainer Ernie Brandts unter, wo er mit einem stark leistungsbezogenen Vertrag ausgestattet wurde. Wider Erwarten fand Mtiliga trotz seiner langen Zwangspause schnell zu seiner Form und entwickelte sich zum unangefochtenen Stammspieler und Leistungsträger. In der Spielzeit 2007/08 avancierte Breda, angeführt von einem starken Mtiliga, zur Überraschungsmannschaft der Saison, drang bis ins Pokalhalbfinale vor und spielte über die gesamte Saison um den Titel in der Eredivisie mit. Innerhalb von eineinhalb Spielzeiten war Mtiliga vom Streichkandidaten bei Feyenoord wieder zu einem begehrten Spieler geworden. Bereits im Oktober 2008 gab er daraufhin bekannt, den Verein zum Saisonende zu verlassen. In Folge spielte er die Saison mit Breda zu Ende, um in der Sommertransferperiode in die Primera División zum FC Málaga zu wechseln.

Wechsel zu Málaga

Bei Málaga konnte er auf Anhieb an seine starken Leistungen bei Breda anknüpfen und erhielt prompt einen Stammplatz als linker Außenverteidiger. Am 24. Januar 2010 im Spiel gegen Real Madrid geriet er ungewollt in den Fokus der Medien, als ihn Cristiano Ronaldo während des Spiels mit einem Ellbogenschlag die Nase brach und dafür die Rote Karte kassierte. Mtiliga musste daraufhin drei Wochen verletzungsbedingt pausieren. Zum Saisonende schaffte Málaga als Tabellensiebzehnter knapp den Verbleib in der Primera División. Aufgrund seiner starken Leistungen wurde Mtiliga daraufhin überraschend von Trainer Morten Olsen in das vorläufige Aufgebot Dänemarks für die Fußball-Weltmeisterschaft 2010 in Südafrika nominiert.