Prime ministers (PMs) significantly contribute to making parliamentary democracy work, but cabinet reshuffles can undermine the PM's ability to perform successfully. New ministers may have less policy expertise, intensify intra-cabinet struggles and hamper the control of government bureaucracy. This article explores the relationship between cabinet reshuffles and prime-ministerial performance in the new democracies of Central and Eastern Europe (CEE). Building on a data set covering 131 cabinets in 11 CEE countries between 1990 and 2018, we find that frequent cabinet reshuffles decrease prime-ministerial performance. In particular, the reshuffling of ministers belonging to other coalition parties than the PM's unfolds a strong negative effect on prime-ministerial performance, while reshuffles in core portfolios and turnover of ministers from the PM party have less negative consequences. These results have important implications for understanding executive politics and government stability in the dynamic environments of CEE democracies and beyond.