Fungal interactions with plant roots, either beneficial or detrimental, have a major impact on agriculture and ecosystems1. The soil inhabiting ascomycete Fusarium oxysporum (Fo) constitutes a species complex of worldwide distribution causing vascular wilt in more than a hundred different crops2,3. Individual isolates of the fungus exhibit host-specific pathogenicity, determined by proteinaceous effectors termed secreted in xylem (SIX)4,5. However, such isolates can also colonize roots of non-host plants asymptomatically as endophytes, or even protect the plant against pathogenic isolates6,7. The molecular determinants of multi-host plant colonization are currently unknown. Here, we identified a set of fungal effectors termed ERCs (Early Root Compatibility effectors), which are secreted during early biotrophic growth of Fo on both host and non-host plants. In contrast to SIX effectors, which are encoded on lineage specific (LS) genomic regions5,8, ERCs are encoded on core genomic regions and broadly conserved across the Fo species complex. Targeted deletion of ERC genes in pathogenic Fo isolate resulted in reduced virulence on the host plant and rapid activation of plant immune responses, while in a non-pathogenic isolate it led to impaired root colonization and loss of biocontrol ability. Strikingly, some ERCs also contribute to Fo infection on the non-vascular land plant Marchantia polymorpha. Our results reveal an evolutionarily conserved mechanism for multi-host colonization by root infecting fungi.