Background - In the subspecies M. avium ssp. paratuberculosis (Map) two groups, known as Cattle (C) and Sheep (S), have been defined by genotyping. Recent studies show that Map C and S have different phenotypes with respect to infection of macrophages and iron metabolism. Map is adapted to the gastrointestinal tract of ruminant, but the mechanism of entry is currently unknown. In this study, we investigated the phenotype of the Map-host interaction, involving the virulence factor heparin-binding hemagglutinin (HBHA), for both groups of Map. HBHA is described in M. tuberculosis as a major adhesin required for extra pulmonary dissemination of the tubercle bacillus. Method - A large collection of Map isolates (types C & S) were genotyped by MIRU-VNTR and RFLP-IS900. The polymorphism of the hbha gene was investigated by fragment analysis using GcneN:apper technology. Structure-functions properties of recombinant HBHA (types C & S) were analyzed by Heparin Sepharose chromatography and SPR analysis based on Biacore technology. Results - In silico analyses of both types of Map have revealed two forms of hbha. This observation, showing that hbha is distinct according to the group, was confirmed using GeneMapper on 83 Map strains (65 Map C & 18 Map S) with various genotypes. We found that Map type C produces HBHA with a short C-terminal domain, while that of typeS presents a long (-terminal domain, similar to that of HBHA produced by M. tuberculosis. The purification of HBHA from Map type C and S by Heparin-sepharose chromatography highlighted a correlation between their affinities to heparin and the length of their C-terminal domain confirmed by Biacore analysis. Conclusion - We show for the first time that the types C and S of Map may be distinguished by the type of HBHA they produce, which differs in size and adherence properties. Thus, HBHA participates in the genotypic and phenotypic differences observed between the C and S types of Map.