The phylogenetic history of Medicago was examined for 60 accessions from 56 species using two nuclear genes (CNGC5 and beta-cop) and one mitochondrial region (rpS14-cob). The results of several analyses revealed that extensive robustly supported incongruence exists among the nuclear genes, the cause of which we seek to explain. After rejecting several processes, hybridization and lineage sorting of ancestral polymorphisms remained as the most likely factors promoting incongruence. Using coalescence simulations, we rejected lineage sorting alone as an explanation of the differences among gene trees. The results indicate that hybridization has been common and ongoing among lineages since the origin of Medicago. Coalescence provides a good framework to test the causes of incongruence commonly seen among gene trees but requires knowledge of effective population sizes and generation times. We estimated the effective population size at 240,000 individuals and assumed a generation time of 1 year in Medicago (many are annual plants). A sensitivity analysis showed that our conclusions remain unchanged using a larger effective population size and/or longer generation time.