MIKC classic (MIKCC)-type MADS-box genes encode transcription factors that function in various developmental processes, including angiosperm floral organ identity. Phylogenetic analyses of the MIKCC-type MADS-box family, including genes from non-flowering plants, suggest that the increased numbers of these genes in flowering plants is related to their functional divergence; however, their precise functions in non-flowering plants and their evolution throughout land plant diversification are unknown. Here, we show that MIKCC-type MADS-box genes in the moss Physcomitrella patens function in two ways to enable fertilization. Analyses of protein localization, deletion mutants and overexpression lines of all six genes indicate that three MIKCC-type MADS-box genes redundantly regulate cell division and growth in the stems for appropriate external water conduction, as well as the formation of sperm with motile flagella. The former function appears to be maintained in the flowering plant lineage, while the latter was lost in accordance with the loss of sperm.