The Mycobacterium avium complex includes two closely related species, Mycobacterium avium and Mycobacterium intracellulare. They are opportunistic pathogens in humans and responsible for severe disease in a wide variety of animals. Yet, little is known about factors involved in their pathogenicity. Here, we identified, purified and characterized adhesins belonging to the heparin-binding hemagglutinin (HBHA) and laminin-binding protein (LBP) family from M. intracellulare ATCC13950 and examined clinical isolates from patients with different pathologies associated with M. intracellulare infection for the presence and conservation of HBHA and LBP. Using a recombinant derivative strain of M. intracellulare ATCC13950 producing green fluorescent protein and luciferase, we found that the addition of heparin inhibited mycobacterial adherence to A549 cells, whereas the addition of laminin enhanced adherence. Both HBHA and LBP were purified by heparin-Sepharose chromatography and their methylation profiles were determined by mass spectrometry. Patients with M. intracellulare infection mounted strong antibody responses to both proteins. By using PCR and immunoblot analyses, we found that both proteins were highly conserved among all 17 examined clinical M. intracellulare isolates from patients with diverse disease manifestations, suggesting a conserved role of these adhesins in M. intracellulare virulence in humans and their potential use as a diagnostic tool.