We analyze collusion in an infinitely repeated Bertrand game, where prices are publicly observed and each firm receives a privately observed, i.i.d. cost shock in each period. Productive efficiency is possible only if high-cost firms relinquish market share. In the most profitable collusive schemes, firms implement productive efficiency, and high-cost firms are favored with higher expected market share in future periods. If types are discrete, there exists a discount factor strictly less than one above which first-best profits can be attained using history-dependent reallocation of market share between equally efficient firms. We also analyze the role of communication and side-payments.