Background: The current model of biology of paratuberculose proposes that after ingestion into the host, Mycobacterium avium subsp. paratuberculosis (MAP) crosses the intestinal barrier via internalization by the M cells. However, MAP may also transcytose the intestinal wall via the enterocytes, but the mechanisms and the bacterial factors involved in this process remain poorly understood. Adhesins such as Heparin-Binding HemAgglutinin (HBHA) and Laminin-Binding Protein (LBP), have been characterized in MAP. Objective: The aim of this study is to determine how these adhesins may promote the bacterial attachment to host cells. To achieve this, we examined the in vitro interaction between MAP and epithelial cells as well as the interaction between the adhesins and extracellular matrix molecules. Methods: MAP cytoadherence assays were performed on epithelial cells A549 in presence or absence of inhibitors. The binding activity of recombinants HBHA and LBP was investigated both by heparin-Sepharose chromatography and by in vitro adherence assays. Results: Cytoadherence assays revealed that pre-incubation of the bacteria in medium containing heparin inhibits the adhesion of MAP to A549 cells. In contrast, addition of laminin to the cell culture supernatant of the infected cells increased the percentage of bacterial adhesion. The in vitro assays confirmed the capacity of HBHA and LBP to promote the attachment of MAP to the extracellular matrix molecules of epithelial cells. Interestingly the adhesins HBHA and LBP expressed by the S and C types of MAP strains are different. This difference may be related to an adaptation to the host preference. Conclusion: We demonstrated that HBHA and LBP express by MAP are involved in its adherence to epithelial cells by two different mechanisms. However, role of these adhesins on MAP entry and survival into the cells remain to be investigated.