Розехнал започва да тренира футбол в местния Сокол Кожушани, преди да отиде в ДЮШ на Сигма Оломоуц. През 1999 г. стига до А отбора и след две години вече е титуляр в защитата на Сигма. През 2003 г. преминава в белгийския Брюж, където в рамките на две години става шампион и носител на купата. Следва трансфер във френския Пари Сен Жермен Още през първия сезон взима участие във всички мачове във Лига 1, печели и купата на страната и е избран за играч на годината в отбора. Добрите изяви водят до интерес от страна на Борусия Дортмунд, Нюкасъл и Севиля. Преди сезон 2007/2008 е закупен от Нюкасъл за 2.9 милиона паунда,[1] с който подписва договор до 2011 г. В края на януари 2008 г. отива под наем в Лацио, а след края на сезона италианският отбор използва опцията за закупуване. През 2009 г. печели Купата на Италия. През лятото на 2009 г. преминава в Хамбургер за 5 милиона евро,[2] където трябва да помогне на защитата, отслабена от контузиите на Алекс Силва и Бастиан Райнхарт.[3]