Multicellular organization arose several times by convergence during the evolution of eukaryotes (e.g., in terrestrial plants, several lineages of "algae," fungi, and metazoans). To reconstruct the evolutionary transitions between unicellularity and multicellularity, we need a proper understanding of the origin and diversification of regulatory molecules governing the construction of a multicellular organism in these various lineages. Homeodomain (HD) proteins offer a paradigm for studying such issues, because in multicellular eukaryotes, like animals, fungi and plants, these transcription factors are extensively used in fundamental developmental processes and are highly diversified. A number of large eukaryote lineages are exclusively unicellular, however, and it remains unclear to what extent this condition reflects their primitive lack of "good building blocks" such as the HD proteins. Taking advantage from the recent burst of sequence data from a wide variety of eukaryote taxa, we show here that HD-containing transcription factors were already existing and diversified (in at least two main classes) in the last common eukaryote ancestor. Although the family was retained and independently expanded in the multicellular taxa, it was lost in several lineages of unicellular parasites or intracellular symbionts. Our findings are consistent with the idea that the common ancestor of eukaryotes was complex in molecular terms, and already possessed many of the regulatory molecules, which later favored the multiple convergent acquisition of multicellularity.