The DMI1, DMI2, and DMI3 genes of Medicago truncatula, which are required for both nodulation and mycorrhization, control early steps of Nod factor signal transduction. Here, we have used diverse approaches to pave the way for the map-based cloning of these genes. Molecular amplification fragment length polymorphism markers linked to the three genes were identified by bulked segregant analysis. Integration of these markers into the general genetic map of M. truncatula revealed that DMI1, DMI2, and DMI3 are located on linkage groups 2, 5, and 8, respectively. Cytogenetic studies using fluorescent in situ hybridization (FISH) on mitotic and pachytene chromosomes confirmed the location of DMI1, DMI2, and DMI3 on chromosomes 2, 5, and 8. FISH-pachytene studies revealed that the three genes are in euchromatic regions of the genome, with a ratio of genetic to cytogenetic distances between 0.8 and 1.6 cM per μm in the DMI1, DMI2, and DMI3 regions. Through grafting experiments, we showed that the genetic control of the dmi1, dmi2, and dmi3 nodulation phenotypes is determined at the root level. This means that mutants can be transformed by Agrobacterium rhizogenes to accelerate the complementation step of map-based cloning projects for DMI1, DMI2, and DMI3.