Tri-methylation of histone H3 lysine 9 is important for recruiting heterochromatin protein 1 (HP1) to discrete regions of the genome, thereby regulating gene expression, chromatin packaging and heterochromatin formation. Here we show that HP1alpha, -beta, and -gamma are released from chromatin during the M phase of the cell cycle, even though tri-methylation levels of histone H3 lysine 9 remain unchanged. However, the additional, transient modification of histone H3 by phosphorylation of serine 10 next to the more stable methyl-lysine 9 mark is sufficient to eject HP1 proteins from their binding sites. Inhibition or depletion of the mitotic kinase Aurora B, which phosphorylates serine 10 on histone H3, causes retention of HP1 proteins on mitotic chromosomes, suggesting that H3 serine 10 phosphorylation is necessary for the dissociation of HP1 from chromatin in M phase. These findings establish a regulatory mechanism of protein-protein interactions, through a combinatorial readout of two adjacent post-translational modifications: a stable methylation and a dynamic phosphorylation mark.