The origin of flowers has puzzled plant biologists ever since Darwin referred to their sudden appearance in the fossil record as an abominable mystery. Flowers are considered to be an assembly of protective, attractive, and reproductive male and female leaf-like organs. Their origin cannot be understood by a morphological comparison to gymnosperms, their closest relatives, which develop separate male or female cones. Despite these morphological differences, gymnosperms and angiosperms possess a similar genetic toolbox consisting of phylogenetically related MADS domain proteins. Using ancestral MADS domain protein reconstruction, we trace the evolution of organ identity quartets along the stem lineage of crown angiosperms. We provide evidence that current floral quartets specifying male organ identity, which consist of four types of subunits, evolved from ancestral complexes of two types of subunits through gene duplication and integration of SEPALLATA proteins just before the origin of flowering plants. Our results suggest that protein interaction changes underlying this compositional shift were the result of a gradual and reversible evolutionary trajectory. Modeling shows that such compositional changes may have facilitated the evolution of the perfect, bisexual flower.