ABSTRACT Identification and characterization of mycobacterial adhesins and complementary host receptors required for colonization and dissemination of mycobacteria in host tissues are needed for a more complete understanding of the pathogenesis of diseases caused by these bacteria and for the development of effective vaccines. Previous investigations have demonstrated that a 28-kDa heparin-binding mycobacterial surface protein, HBHA, can agglutinate erythrocytes and promote mycobacterial aggregation in vitro. In this study, further molecular and biochemical analysis of HBHA demonstrates that it has three functional domains: a transmembrane domain of 18 amino acids residing near the N terminus, a large domain of 81 amino acids consistent with an α-helical coiled-coil region, and a Lys-Pro-Ala-rich C-terminal domain that mediates binding to proteoglycans. Using His-tagged recombinant HBHA proteins and nickel chromatography we demonstrate that HBHA polypeptides which contain the coiled-coil region form multimers. This tendency to oligomerize may be responsible for the induction of mycobacterial aggregation since a truncated N-terminal HBHA fragment containing the coiled-coil domain promotes mycobacterial aggregation. Conversely, a truncated C-terminal HBHA fragment which contains Lys-Pro-Ala-rich repeats binds to the proteoglycan decorin. These results indicate that HBHA contains at least three distinct domains which facilitate intercalation into surface membranes, promote bacterium-bacterium interactions, and mediate the attachment to sulfated glycoconjugates found in host tissues.