ドイツ民主共和国のツィッタウに生まれる。1985年にアビトゥーア合格。兵役の際シュタージで警護員を務め、そのまま職員として残った。1986年にドイツ社会主義統一党（SED）に入党。ハイルマンによれば、1989年10月にシュタージに退職願を出したという。一方でそれはベルリンの壁崩壊後の同年11月以後のことだったとする報道もある。シュタージ解体に伴い、1990年1月にハイルマンはシュタージから離れた。
1991年からSEDの後身である民主社会党（PDS）のツィッタウ支部事務局で働き始める。一方で1991年にツィッタウ技術高等専門学校で経済学を学び始める。1年後にベルリン自由大学に転学し、法学を学んだ。同年、PDSを離党。1997年からはキール大学に転じる。2000年にPDSに再入党し、党の北西メックレンブルク支部代表委員となる。2004年に法学士号を取得して卒業。2005年にリューベック地方裁判所で司法修習を始め、同時に党リューベック支部に入った。同年に行われた2005年ドイツ連邦議会選挙ではシュレースヴィヒ＝ホルシュタイン州の比例代表リスト入りし、比例代表で当選した。このため司法修習は中断した。
当選後の2005年10月、「デア・シュピーゲル」誌はハイルマンがシュタージの職員であったことを報じた。ハイルマンは「兵役の延長として」職員であったことを認めている。シュタージ問題の専門家は、ハイルマンの説明は受け入れがたいとし、警護官は党の要人を武装して警護する専門職員であり、シュタージの被害を受けた国民からすればこのような経歴をもつ人物が連邦議会に選良として座っているのは耐え難い、としている。ハイルマンは選挙前には党友のごく数人にしか自分がシュタージに居たことを明かしていなかった。これは党規に反するものであったため、2005年12月にPDSシュレースヴィヒ＝ホルシュタイン支部はハイルマンに対し不信任投票を実施した。結果は47：42で信任された。
2006年、ハイルマンは自身が同性愛者であることをカミングアウトした。そのため党内ではクィア・グループに属している。2008年11月、リューベック地方裁判所に対し、ドイツ語版ウィキペディアの記述内容が事実に反し、自分がそれに対する反論をする機会が与えられていないことを理由に、ドイツ語版ウィキペディアとドイツ語版ウィキメディアの差し止めを行う仮申請を行った。記述内容が変更されたのち、請求を撤回し、「短慮であった」とする声明を出した。この行動に対し、党友からも法の軽々しい利用や技術に対する無理解を批判する声が上がった。
2009年ドイツ連邦議会選挙では党内投票に敗れて比例代表リスト入りすることができず、出馬出来なかったため議席を失った。
