Dopo aver militato nelle giovanili di Sigma Holodany, Sokol Holice, Lokomotiva Olomouc e Sigma Olomouc, nella stagione 1996-1997 ha debuttato tra i professionisti nelle file del Sigma Olomouc. Dopo un periodo all'Atlantic Lázně Bohdaneč, ha militato nelle file del Sigma Olomouc per tre stagioni, totalizzando 66 presenze e 17 reti in campionato. Nel 2000 si è trasferito in Germania, all'Amburgo. Ha militato nelle file dei Dinasaurier per due stagioni e mezzo, totalizzando 6 reti in 64 presenze. Nel gennaio 2003 si è trasferito in prestito all'Arminia Bielefeld, con cui ha totalizzato 14 presenze. Nel luglio 2003 è tornato in patria, trasferendosi al Baník Ostrava[1]. La stagione con il Baník Ostrava è stata particolarmente positiva per Heinz: ha segnato 19 reti in 30 presenze di campionato ed è stato il capocannoniere del torneo. Nell'agosto 2004 è tornato in Germania, al Borussia M'gladbach[2]. Il 31 agosto 2005 si è trasferito in Turchia, al Galatasaray[3]. Ha militato nelle file del club turco per una stagione, totalizzando 24 presenze e 4 reti. Dopo aver rescisso con il Galatasaray, nel settembre 2006 è stato ingaggiato dal Saint-Étienne[4], club francese. Il 21 agosto 2007 è passato al Nantes[5]. Nel settembre 2008 è tornato in patria, firmando con lo Zbrojovka Brno[6][7]. Nel 2009 si è trasferito in Austria, al Kapfenberger[8]. Nel luglio 2010 ha firmato un contratto annuale con il Ferencváros[9]. Nella stagione successiva è tornato al Sigma Olomouc[10]. Nel novembre 2012 ha rescisso il proprio contratto[11]. Rimasto svincolato, nel gennaio 2013 è passato allo Znojmo[12]. Ha concluso la propria carriera nel 2016, dopo due esperienze all'1. HFK Olomouc e una in Austria con il Melk[13].
Rep. Ceca
Amburgo
Galatasaray
Saint-Étienne
Kapfenberger
Ferencváros
Wikimedia Commons contiene immagini o altri file su Marek Heinz