Anfänge in Recke und Osnabrück

Heider begann seine Karriere beim TuS Recke und wechselte 2003 in die Jugendabteilung des VfL Osnabrück, bei dem er im Januar 2006 seinen ersten Profivertrag unterschrieb. In der Saison 2005/06 konnte er für die Profimannschaft in der Regionalliga Nord in 16 Spielen zwei Tore erzielen, für die zweite Mannschaft, die in der Oberliga Nord spielte, erzielte er in 25 Partien stolze 18 Tore.

Werder Bremen II

Auf Grund seiner starken Leistungen wechselte er zur neuen Saison zu Werder Bremen II in die Regionalliga Nord, wo ihm in seiner Debütsaison auf Anhieb sechs Saisontore gelangen. Ein Jahr später gelangen ihm neun Treffer. Zur Saison 2008/09 wurde die 3. Liga gegründet, für die sich Werder Bremen II qualifizierte. Er konnte in diesem Jahr die Leistungen aus den Vorjahren nicht bestätigen und hatte am Saisonende lediglich ein Tor erzielt, weshalb er in der neuen Saison zum Aufsteiger Holstein Kiel wechselte.

Holstein Kiel

In Kiel schaffte es Heider im ersten Jahr nicht, sich einen Stammplatz zu erobern, weshalb er kurzfristig für die zweite Mannschaft von Holstein Kiel, die in der Schleswig-Holstein-Liga spielte, auflief. In der 3. Liga kam er nur auf zwei Tore und stieg gemeinsam mit seiner Mannschaft nach nur einem Jahr wieder in die Regionalliga Nord ab. In der Saison 2010/11 gelang ihm dann unter Trainer Thorsten Gutzeit der Durchbruch. Er spielte sich in der Vorbereitung in die Startelf, profitierte dabei allerdings auch von der Verletzung von Stammspieler Tim Wulff. In der Hinrunde gelang dem Stürmer mit sieben Toren eine gute Ausbeute, die er durch elf weitere Tore in der Rückrunde noch steigern konnte. Heider kam auf 30 Saisonspiele, neben den 18 Saisontoren legte er seinen Mitspielern zudem elf Tore auf (eine Quote von 0,96 Scorerpunkten pro Spiel). Die Mannschaft beendete die Saison auf Platz 6, gewann aber gegen den Erzrivalen vom VfB Lübeck das Schleswig-Holstein Pokalfinale und qualifizierte sich somit für den DFB-Pokal.

Marc Heider verlängerte seinen zum Saisonende auslaufenden Vertrag mit Holstein Kiel, obwohl ihm Angebote aus der 3. Liga und der 2. Bundesliga vorlagen. Mit neun Toren in der Hinrunde der Saison 2011/12 war Heider erneut bester Torschütze der Kieler und holte mit dem Verein die Herbstmeisterschaft der Regionalliga. Im DFB-Pokal 2011/12 erreichte der Angreifer mit seinem Klub nach Siegen u. a. über den MSV Duisburg und den 1. FSV Mainz 05 das Viertelfinale. Nach Ende der Saison 2015/16, in der er drei Tore erzielte, wurde Heider trotz seines noch bis 2017 laufenden Vertrags bei Holstein Kiel freigestellt.

Rückkehr nach Osnabrück

Schon wenige Tage später, kurz nach seinem 30. Geburtstag, wurde die Rückkehr des Stürmers zu seinem ersten Profiverein VfL Osnabrück bekannt. Heider unterschrieb dort einen Zwei-Jahres-Vertrag. Wegen der Verwicklung in einen Manipulationsversuch im Vorfeld des letzten VfL-Saisonspiels 2016/17 gegen den SC Paderborn 07, der von Tobias Willers ausging und an dem auch Addy-Waku Menga beteiligt war, wurde Heider in der Sommerpause 2017 durch das DFB-Sportgericht wegen „unsportlichen Verhaltens“ zu vier Spielen Sperre sowie einer Geldstrafe von 2000 Euro verurteilt. Sein Vertrag hat sich 2018 durch eine Vertragsoption um ein Jahr verlängert. In der Sommerpause 2018 wurde Heider von Trainer Daniel Thioune zum neuen Mannschaftskapitän der Lila-Weißen bestimmt. Im Januar 2019 erhielt er eine erneute Vertragsverlängerung, dieses Mal bis Juni 2021, und stieg im gleichen Jahr mit dem VfL als Meister in die 2. Bundesliga auf. Sein erstes Tor in der 2. Bundesliga schoss Heider am 14. März 2021 im Spiel gegen den 1. FC Nürnberg (Endstand 1:1). Zum Ende der Saison 2020/21 stieg er mit dem VfL in der Relegation gegen den FC Ingolstadt 04 in die 3. Liga ab.

Anfang Mai 2023 gab Heider bekannt, seine Karriere als Profifußballer nach der Saison 2022/23 zu beenden. Im letzten Drittliga-Saisonspiel gegen Borussia Dortmund II schaffte er mit dem VfL durch einen 2:1-Sieg den Wiederaufstieg in die 2. Bundesliga.

Sportfreunde Lotte

Zur Saison 2023/24 wechselt Marc Heider zu den Sportfreunden Lotte in die fünftklassige Oberliga Westfalen, wo er zugleich als Spieler und als Co-Trainer eingesetzt wird (Spielertrainer).