Di padre [[Roma|romano]](la famiglia Flamini, senza accento, è originaria dei Vallecupola, frazione di Roccasinibalda in provincia di Rieti) e madre [[Corsica|corsa]],<ref>{{cita web |url=http://www.independent.co.uk/sport/football/european/mathieu-flamini-we-have-to-be-at-the-front-of-the-physical-battle-if-we-have-to-fight-we-fight-784218.html |titolo=Mathieu Flamini: "We have to be at the front of the physical battle... if we have to fight, we fight" |editore=independent.co.uk |lingua=en |data=20-02-2008 |accesso=13-06-2008}}</ref> è cresciuto calcisticamente nell'[[Olympique de Marseille|Olympique Marsiglia]] e ha esordito in prima squadra il [[23 dicembre]] [[2003]] in una partita di [[Ligue 1]] contro il [[Toulouse FC|Tolosa]] (1-0 per i [[Marsiglia|marsigliesi]]). Nella stessa stagione si è fatto notare al livello internazionale grazie alla 9 partite disputate in [[Coppa UEFA]], in cui ha debuttato il [[26 febbraio]] [[2004]] entrando al 74° minuto contro il [[Dnipro Dnipropetrovsk|Dnipro]] (1-0) e in cui ha disputato anche la finale che persa 2-0 dall'Olympique Marsiglia a [[Göteborg]] contro il [[Valencia Club de Fútbol|Valencia]]. A fine stagione Flamini ha rifiutato il contratto da professionista propostogli dall'Olympique Marsiglia e si è trasfeito all'[[Arsenal Football Club|Arsenal]] allenato dal connazionale [[Arsène Wenger]].
