In flowering plants, arguably the most significant transcription factors regulating development are MADS-domain proteins, encoded by Type I and Type II MADS-box genes. Type II genes are divided into the MIKC(C) and MIKC* groups. In angiosperms, these types and groups play distinct roles in the development of female gametophytes, embryos, and seeds (Type I); vegetative and floral tissues in sporophytes (MIKC(C)); and male gametophytes (MIKC*), but their functions in other plants are largely unknown. The complete set of MADS-box genes has been described for several angiosperms and a moss, Physcomitrella patens. Our examination of the complete genome sequence of a lycophyte, Selaginella moellendorffii, revealed 19 putative MADS-box genes (13 Type I, 3 MIKC(C), and 3 MIKC*). Our results suggest that the most recent common ancestor of vascular plants possessed at least two Type I and two Type II genes. None of the S. moellendorffii MIKC(C) genes were identified as orthologs of any floral organ identity genes. This strongly corroborates the view that the clades of floral organ identity genes originated in a common ancestor of seed plants after the lineage that led to lycophytes had branched off, and that expansion of MIKC(C) genes in the lineage leading to seed plants facilitated the evolution of their unique reproductive organs. The number of MIKC* genes and the ratio of MIKC* to MIKC(C) genes is lower in S. moellendorffii and angiosperms than in P. patens, correlated with reduction of the gametophyte in vascular plants. Our data indicate that Type I genes duplicated and diversified independently within lycophytes and seed plants. Our observations on MADS-box gene evolution echo morphological evolution since the two lineages of vascular plants appear to have arrived independently at similar body plans. Our annotation of MADS-box genes in S. moellendorffii provides the basis for functional studies to reveal the roles of this crucial gene family in basal vascular plants.