Sister chromatids are held together by the ring-shaped cohesin complex, which likely entraps both DNA-double strands in its middle. This tie is resolved in anaphase when separase, a giant protease, becomes active and cleaves the kleisin subunit of cohesin. Premature activation of separase and, hence, chromosome missegregation are prevented by at least two inhibitory mechanisms. Although securin has long been appreciated as a direct inhibitor of separase, surprisingly its loss has basically no phenotype in mammals. Phosphorylation-dependent binding of Cdk1 constitutes an alternative way to inhibit vertebrate separase. Its importance is illustrated by the premature loss of cohesion when Cdk1-resistant separase is expressed in mammalian cells without or with limiting amounts of securin. Here, we demonstrate that crucial inhibitory phosphorylations occur within a region of human separase that is also shown to make direct contact with the cyclin B1 subunit of Cdk1. This region exhibits a weak homology to Saccharomyces cerevisiae Cdc6 of similar Cdk1 binding behavior, thereby establishing phosphoserine/threonine-mediated binding of partners as a conserved characteristic of B-type cyclins. In contrast to the Cdc6-like domain, the previously identified serine 1126 phosphorylation is fully dispensable for Cdk1 binding to separase fragments. This suggests that despite its in vivo relevance, it promotes complex formation indirectly, possibly by inducing a conformational change in full-length separase.