Richard Dostálek karierę rozpoczął w Zbrojovce Brno. W 1994 roku został wybrany Największym Talentem w Czeskiej Lidze[1]. W 1998 roku za 20 milionów koron trafił do Slavii Praga. Był to wówczas najwyższy transfer w historii Zbrojovki. W latach 1999 i 2002 zdobył ze Slavią Puchar Czech.