We consider a dynamic Bertrand game in which prices are publicly observed and each firm receives a privately observed cost shock in each period. Although cost shocks are independent across firms, within a firm costs follow a first-order Markov process. We analyze the set of collusive equilibria available to firms, emphasizing the best collusive scheme for the firms at the start of the game. In general, there is a trade-off between productive efficiency, whereby the low-cost firm serves the market in a given period, and high prices. We show that when costs are perfectly correlated over time within a firm, if the distribution of costs is log-concave and firms are sufficiently patient, then the optimal collusive scheme entails price rigidity: firms set the same price and share the market equally, regardless of their respective costs. When serial correlation of costs is imperfect, partial productive efficiency is optimal. For the case of two cost types, first-best collusion is possible if the firms are patient relative to the persistence of cost shocks, but not otherwise. We present numerical examples of first-best collusive schemes.