Mělnický rodák udělal první hokejové krůčky v pěti letech. Na zimní stadion jej přivedl otec, který také hrával hokej. V Mělníku vydržel Podlešák do třetí třídy, pak přestoupil do Sparty.

V roce 2000 se zúčastnil prvního velkého turnaje s národním týmem, na mistrovství světa hráčů do osmnácti let ve Švýcarsku skončili však Češi až šestí. Na šampionátu zaujal zámořské skauty nejen svou robustní postavou, ale taktéž výborným bruslením a skvělou orientací v brankovišti soupeře. Není tedy divu, že se v létě vydal za lepší soutěží, zakotvil v týmu Tri City Americans hrajícím Western Hockey League.

Během sezony přestoupil do Lethbridge Hurricanes, kde si zahrál i v play-off. Po vydařené sezoně následoval draft, kde si jej v druhém kole vybral Phoenix jako celkově pětačtyřicátého hráče. V týmu Lethbridge strávil i sezonu 2001–02, kdy měl dokonce průměr bodu na zápas. Již tehdy ho však přibrzdily zdravotní potíže. V následujících třech letech ho zranění a nemoci brzdily napokračování a Podlešák tak musel vynechat podstatné části sezon. V nich působil ve farmářské AHL a nejlépe se mu dařilo v té poslední, kdy působil v San Antoniu.

Dokonce už to vypadalo, že si ho „Kojoti vytáhnou do NHL, ale přišel otřes mozku a Podlešák byl rád, že nemusel skončit s hokejem.

Po překonání zdravotních problému se vysoký útočník rozhodl v létě 2006 pro návrat do Sparty. Ač moc nehrál, pomohl k obhajobě sparťanského titulu sedmi body. Ani ve Spartě se mu nevyhnuly zdravotní trable, vynechal kvůli nim celou řadu zápasů. Úplně zdravý nebyl ani rok následující, ale tentokrát už odehrál 41 zápasů a velmi se mu dařilo zejména na turnaji Super Six, kde dokázal skórovat i ve finále. Trenér Výborný mu věří zejména v defenzivní činnosti, často týmu pomáhá v oslabení.

Martin Podlešák started his career in his hometown Mělník at the age of 5. A few years later he came to Sparta. During the U18 World Championship in 2000 Podlešák attracted the NHL scouts and after being drafted by the Phoenix Coyotes as number 45 overall he moved across the ocean. He played in WHL but due to the frequent health problems including the concussion he never had the opportunity to play in the famous NHL. In 2006 he decided to return home. But either during the 2006–07 season he didn t avoid health troubles, next year it was just a little better, he played 45 games, scored one goal in finals on Super Six tournament.