The binding and ingestion of Mycobacterium avium subsp. paratuberculosis (MAP) by host cells are fibronectin (FN) dependent. In several species of mycobacteria, a specific family of proteins allows the attachment and internalization of these bacteria by epithelial cells through interaction with FN. Thus, the identification of adhesion molecules is essential to understand the pathogenesis of MAP. The aim of this study was to identify and characterize FN binding cell wall proteins of MAP. We searched for conserved adhesins within a large panel of surface immunogenic proteins of MAP and investigated a possible interaction with FN. For this purpose, a cell wall protein fraction was obtained and resolved by 2D electrophoresis. The immunoreactive spots were identified by MALDI-TOF MS and a homology search was performed. We selected elongation factor Tu (EF-Tu) as candidate for further studies. We demonstrated the FN-binding capability of EF-Tu using a ligand blot assay and also confirmed the interaction with FN in a dose-dependent manner by ELISA. The dissociation constant of EF-Tu was determined by surface plasmon resonance and displayed values within the μM range. These data support the hypothesis that this protein could be involved in the interaction of MAP with epithelial cells through FN binding.