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. Method - A large collection of Map isolates (types C & S) genotyped were used to investigate the polymorphism of the hbhA gene by GeneMapper. The biochemical features of HBHA produced by these two types were analyzed by Heparin-Sepharose Chromatography (HSC) and Surface Plasmon Resonance (SPR). 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 94 Map strains (76 Map C & 18 MapS) with various genotypes. We found that Map C produces HBHA with a short C-terminal domain, while that of type S presents a long C-terminal domain, similar to that of HBHA produced by M. tuberculosis. The purification of recombinant HBHA from Map C and S by HSC, highlighted a correlation between their affinities to heparin and the length of their C-terminal domain, which has been quantified by SPR. 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. Thus, HBHA participates in the genotypic and phenotypic differences observed between the C and S types of Map.