During meiosis, cohesins--protein complexes that hold sister chromatids together--are lost from chromosomes in a step-wise manner. Loss of cohesins from chromosome arms is necessary for homologous chromosomes to segregate during meiosis I. Retention of cohesins around centromeres until meiosis II is required for the accurate segregation of sister chromatids. Here we show that phosphorylation of the cohesin subunit Rec8 contributes to step-wise cohesin removal. Our data further implicate two other key regulators of meiotic chromosome segregation, the cohesin protector Sgo1 and meiotic recombination in bringing about the step-wise loss of cohesins and thus the establishment of the meiotic chromosome segregation pattern. Understanding the interplay between these processes should provide insight into the events underlying meiotic chromosome mis-segregation, the leading cause of miscarriages and mental retardation in humans.