The tropical legume Sesbania rostrata provides its microsymbiont Azorhizobium caulinodans with versatile invasion strategies to allow nodule formation in temporarily flooded habitats. In aerated soils, the bacteria enter via the root hair curling mechanism. Submergence prevents this epidermal invasion by accumulation of inhibiting concentrations of ethylene and, under these conditions, the bacterial colonization occurs via intercellular cortical infection at lateral root bases. The transcriptome of both invasion ways was compared by cDNA-amplified fragment length polymorphism analysis. Clusters of gene tags were identified that were specific for either epidermal or cortical invasion or were shared by both. The data provide insight into mechanisms that control infection and illustrate that entry via the epidermis adds a layer of complexity to rhizobial invasion.