Pathogenic bacteria use protein adhesins to infect the ciliated respiratory epithelia of vertebrate hosts. In this work, we show that the filamentous hemagglutinin FhaB adhesin of carries a C-terminal microtubule-binding domain (FhaB-CT), which is translocated into host cells to promote colonization. FhaB-CT delivery is required to occupy a niche at the base of cilia in airway epithelia, and mutant bacteria lacking this domain are defective for nasal colonization. These observations suggest that FhaB-CT is transferred into motile respiratory cilia to interact with core axonemal microtubules. We propose that adheres initially to the tips of cilia and then deploys multiple FhaB adhesins to migrate to the base of the cilia forest, where the bacteria resist removal by the mucociliary "escalator" that normally clears the respiratory tract of microbes.