The genome of Arabidopsis (Arabidopsis thaliana) encodes over 100 MADS-domain transcription factors, categorized into five phylogenetic subgroups. Most research efforts have focused on just one of these subgroups (MIKC(c)), whereas the other four remain largely unexplored. Here, we report on five members of the so-called Mdelta or Arabidopsis MIKC* (AtMIKC*) subgroup, which are predominantly expressed during the late stages of pollen development. Very few MADS-box genes function in mature pollen, and from this perspective, the AtMIKC* genes are therefore highly exceptional. We found that the AtMIKC* proteins are able to form multiple heterodimeric complexes in planta, and that these protein complexes exhibit a for the MADS-family unusual and high DNA binding specificity in vitro. Compared to their occurrence in promoters genome wide, AtMIKC* binding sites are strongly overrepresented in the proximal region of late pollen-specific promoters. By combining our experimental data with in silico genomics and pollen transcriptomics approaches, we identified a considerable number of putative direct target genes of the AtMIKC* transcription factor complexes in pollen, many of which have known or proposed functions in pollen tube growth. The expression of several of these predicted targets is altered in mutant pollen in which all AtMIKC* complexes are affected, and in vitro germination of this mutant pollen is severely impaired. Our data therefore suggest that the AtMIKC* protein complexes play an essential role in transcriptional regulation during late pollen development.