In den Niederlanden

Mathijsen spielte zunächst bei VOAB in seiner Geburtsstadt Goirle, einem Vorort der im Süden der Niederlande gelegenen Großstadt Tilburg. Als Neunjähriger wechselte er zu Willem II Tilburg und durchlief dort die weiteren Jugendmannschaften, bis er 1998/99 im Aufgebot der ersten Mannschaft in der niederländischen Eredivisie stand. 1999 hatte er seinen ersten Erstligaauftritt. Nachdem der Abwehrspieler im folgenden Jahr schon öfter eingesetzt worden war, konnte er sich im dritten Jahr endgültig durchsetzen. Von 2001 bis 2004 war er Stammspieler in der Abwehrmitte und bestritt fast alle Pflichtspiele für den Verein.

Seinen Durchbruch hatte Mathijsen nach seinem Wechsel zum AZ Alkmaar. Zusammen mit Tim de Cler und Kew Jaliens bildete er ein Abwehrtrio, das zu dieser Zeit auch zum Teil die Abwehr in der niederländischen Nationalmannschaft darstellte. In seiner ersten Saison mit den Nordholländern belegte der Verein den dritten Platz und erreichte im UEFA-Pokal das Halbfinale.

Hamburger SV

Am 23. August 2006 wechselte Mathijsen zum deutschen Bundesligaverein Hamburger SV. Am 27. August 2006 debütierte er am dritten Spieltag im Spiel gegen Hertha BSC in der Anfangself. Mathijsen erkämpfte sich einen Stammplatz und wurde dabei überwiegend als Innenverteidiger eingesetzt; in seiner ersten Saison stand er in allem 32 Bundesliga-Spielen auf dem Feld und war dabei in fast allen Partien Teil der Startelf. Der Hamburger SV nahm in dieser Spielzeit in der UEFA Champions League teil, schied allerdings dort nach der Gruppenphase aus. In der Liga spielte der Verein zunächst gegen den Abstieg und stand zur Winterpause auf dem 17. Tabellenplatz und nachdem Trainer Thomas Doll nach einem 1:1-Unentschieden gegen den Aufsteiger FC Energie Cottbus – der HSV rutschte dadurch auf den letzten Platz ab – durch Huub Stevens ersetzt wurde, folgte eine Leistungssteigerung, die sowohl in den Klassenerhalt als auch in die Qualifikation der Norddeutschen für den UI-Cup mündeten. Am 20. Oktober 2007 erzielte Mathijsen im Spiel gegen den VfB Stuttgart sein erstes Bundesligator und zugleich den 2500. Treffer des HSV in der Bundesliga. Er blieb weiterhin Stammspieler, wobei er drei Partien in der Liga wegen einer Rotsperre verpasst hatte. Mit dem HSV qualifizierte sich Mathijsen über den UI-Cup für den UEFA-Pokal, in der sie das Achtelfinale erreichten und dort gegen den Ligakonkurrenten Bayer 04 Leverkusen ausschieden. In der Liga stand der Verein über weite Strecken der Saison auf einem Platz für die internationalen Wettbewerbe und qualifizierte sich schlussendlich für den UEFA-Pokal. In der Saison 2008/09 der Hamburger SV phasenweise Tabellenführer und da sie zudem das UEFA-Pokalhalbfinale als auch die Runde der letzten vier im DFB-Pokal erreicht hatten, spielten sie um drei Titel mit, doch in allen drei Wettbewerben mussten Mathijsen und sein Verein sich dem Erzrivalen SV Werder Bremen geschlagen geben und in der Endphase der Saison drohte der HSV sogar die Teilnahme für das internationale Geschäft zu verpassen, allerdings wurden die Norddeutschen Fünfter und qualifizierten sich somit für die neugegründete UEFA Europa League. In Mathijsens vierter Saison in der norddeutschen Millionenmetropole Hamburg erreichte der Verein im genannten Wettbewerb das Halbfinale und schied dort gegen den FC Fulham aus, womit das Endspiel im eigenen Stadion verpasst wurde. Zudem verpassten sie in der Liga die abermalige Teilnahme am internationalen Geschäft. Mathijsen blieb noch ein Jahr und verpasste mit seinem Verein zum zweiten Mal in Folge die Teilnahme für den europäischen Wettbewerb. In der Folge verließ er nach fünf Jahren den Verein.

FC Málaga und Karriereende in den Niederlanden

Im Sommer 2011 wechselte Mathijsen zum FC Málaga. Er unterschrieb beim spanischen Erstligisten einen Zweijahresvertrag mit Option auf ein weiteres Jahr. Bei den Andalusiern blieb er jedoch nur eine Saison, bestritt in dieser 28 Ligaspiele und drei Pokalspiele und erreichte mit seiner Mannschaft den vierten Platz, im Pokal schied Malaga im Achtelfinale gegen Real Madrid aus.

Zur Saison 2012/13 wechselte er zurück in die Niederlande zu Feyenoord Rotterdam. Er unterschrieb dort einen Vertrag über drei Spielzeiten. In der Saison 2013/14 wurde er mit Feyenoord Vizemeister. In seiner letzten Saison erreichte er mit der Mannschaft – nach zweimaligem Scheitern in der Qualifikation in den Vorsaisons – schließlich die Gruppenphase der Europa League 2014/15 und wurde dort in einem Spiel eingesetzt. Bis Ende der Saison 2014/15 absolvierte er für Feyenoord insgesamt 57 Ligaspiele (ein Tor). Nach Saisonende verließ Mathijsen den Verein und beendete zum Jahreswechsel 2015/16 seine aktive Karriere.