Early embryonic cell cycles in Drosophila consist of rapidly alternating S and M phases. Three genes, pan gu (png), plutonium (plu), and giant nuclei (gnu) coordinate these early S-M cycles by ensuring adequate Cyclin B protein levels. Mutations in any of these genes result in unregulated DNA replication and a lack of mitosis ("giant nuclei" phenotype). png encodes a serine/threonine protein kinase, and plu and gnu encode small, novel proteins. We show that PNG, PLU, and GNU constitute a novel protein kinase complex that specifically regulates S-M cell cycles. All three proteins are required for PNG kinase activity and are phosphorylated by PNG in vitro. Yeast two-hybrid screening revealed a direct interaction between PNG and PLU, and their co-expression is required for physical association and activation of PNG kinase. Artificial dimerization of PLU via fusion to either GST or FK506 binding protein (in the presence of dimerizing agent) abrogates the requirement for GNU to activate PNG kinase. We propose a model in which GNU normally regulates embryonic cell cycles by promoting transient dimerization of a core PNG/PLU complex, thereby stimulating PNG kinase activity.