Il commence sa carrière en 1995 au sein de l'équipe junior de sa ville natale, le HC Vajgar Hradec. Deux saisons plus tard, il fait ses débuts dans le championnat Élite de seconde division, la 1.liga. La saison suivante, il rejoint le club du HC Třinec avec qui il va jouer dans toute la saison en équipe sénior.
Lors de la saison 1999-2000, il connaît de nombreux clubs commençant la saison avec Třinec et la finissant au sein de sa première équipe en 2.liga. Par la suite, il joue jusqu'à la fin de la saison 2002-2003 dans l’Extraliga pour le HC Třinec et il participe au repêchage d'entrée dans la Ligue nationale de hockey cette même année. Il est choisi lors de la huitième ronde par les Rangers de New York, 243e choix, alors qu'il venait de finir meilleur buteur de la saison d'Extraliga avec 32 réalisations.
Il quitte alors le club de Třinec pour rejoindre le HC Sparta Prague pour qui il évolue pendant trois saisons, dont la dernière victorieuse. En effet, l'équipe remporte son troisième titre de République tchèque alors que Marek remporte son premier titre de meilleur pointeur de la saison avec 54 points. Il finit également avec un différentiel plus-moins de +25, le meilleur de la ligue.