MADS-box genes encode regulatory factors that are involved at various stages in plant development. These genes function not only during early floral meristem identity, but also when the fate of floral organ primordia is determined in a later step. Here, we screened a floral bud cDNA library to isolate a tobacco MADS-box gene, NtMADS4, using the rice MADS-box gene, OsMADS1, as a probe. We previously reported that OsMADS1 plays a critical role in flower development in rice. Ectopic expression of NtMADS4 caused phenotypes of extremely early flowering as well as dwarfism. Plant MADS proteins have a K domain that mediates the formation of dimers. This dimerization appears to be an essential step for a functional protein complex. NtMADS11 was isolated as an interacting partner of NtMADS4 by yeast two-hybrid screening. The latter was included in the AGAMOUS-like 2 (AGL2) family whereas the former was categorized in the SQUAMOSA (SQUA) family. While the transcript of NtMADS4 was detectable only in reproductive organs, that of NtMADS11 was seen in both reproductive and vegetative organs. Expression levels were high for both genes during early developmental stages. Ectopic expression of NtMADS11 and OsMADS14 was able to rescue the floral organ defects seen in the strong ap1-1 mutant. Roles of NtMADS4 and NtMADS11 in the floral initiation are discussed.