Matmour began his playing career at his hometown club of RC Strasbourg. After coming up through the academy team, he was not offered a professional contract. He subsequently briefly played for the amateur side Vauban Strasbourg before leaving to Germany to join SC Freiburg's reserve side. He was eventually promoted to the senior side, where he made 80 league appearances in three seasons in the 2. Bundesliga.
On 1 August 2010, during Mönchengladbach's arranged friendly match versus Liverpool as part of their 110th anniversary celebrations at Borussia Park, Matmour took advantage of some poor play by Daniel Ayala inside the area and produced a powerful finish in the eighth minute. They won the contest thanks to Matmour's goal, with the final score being 1–0.
On 30 January 2011, Matmour came on as a substitute for Mike Hanke in the forty-sixth minute in a league fixture against Eintracht Frankfurt. In the second half, Matmour came close to scoring with a header which bounced off the top of the crossbar. He set up the only goal scored in the encounter which was a cross from the left side to Igor de Camargo, who put the ball away inside the far right post.
On 1 July 2011, Matmour signed a one-year contract, with Eintracht holding the option of a further two-year extension. The two clubs agreed not to release the transfer fee, therefore keeping it undisclosed. Eintracht chairman Heribert Bruchhagen said "In signing Karim Matmour we've found the optimal solution for the vacant slot on the right of the attack, in line with (coach) Armin Veh's wishes", about the signing of Matmour.