Cell division and development are regulated by networks of kinases and phosphatases. In early Drosophila embryogenesis, 13 rapid nuclear divisions take place in a syncytium, requiring fine coordination between cell cycle regulators. The Polo kinase is a conserved, crucial regulator of M-phase. We have recently reported an antagonism between Polo and Greatwall (Gwl), another mitotic kinase, in Drosophila embryos. However, the nature of the pathways linking them remained elusive. We have conducted a comprehensive screen for additional genes functioning with polo and gwl. We uncovered a strong interdependence between Polo and Protein Phosphatase 2A (PP2A) with its B-type subunit Twins (Tws). Reducing the maternal contribution of Polo and PP2A-Tws together is embryonic lethal. We found that Polo and PP2A-Tws collaborate to ensure centrosome attachment to nuclei. While a reduction in Polo activity leads to centrosome detachments observable mostly around prophase, a reduction in PP2A-Tws activity leads to centrosome detachments at mitotic exit, and a reduction in both Polo and PP2A-Tws enhances the frequency of detachments at all stages. Moreover, we show that Gwl antagonizes PP2A-Tws function in both meiosis and mitosis. Our study highlights how proper coordination of mitotic entry and exit is required during embryonic cell cycles and defines important roles for Polo and the Gwl-PP2A-Tws pathway in this process.