Binding of Mycobacterium leprae to and invasion of Schwann cells (SC) represent a crucial step that initiates nerve damage in leprosy. We and others have described that M. leprae colonization of the peripheral nerve system may be mediated in part by a surface-exposed histone-like protein (Hlp), characterized as a laminin-binding protein (LBP). Hlp/LBP has also been shown to play a role in the binding of mycobacteria to alveolar epithelial cells and macrophages. In the present study we report that M. leprae expresses Hlp/LBP protein during the course of human infection. Additionally, we analyzed the interaction of Hlp/LBP with the extracellular matrix and host cell surface. We show that Hlp/LBP, besides laminin, also binds heparin and heparan sulfate. Testing truncated recombinant Hlp molecules corresponding to the N-terminal (rHlp-N) and the C-terminal (rHlp-C) domains of the protein, we established that interaction of Hlp/LBP with laminin-2 and heparin is mainly mediated by the C-terminal domain of the protein. Moreover, the same domain was found to be involved in Hlp/LBP-mediating bacterial binding to human SC. Finally, evidence is shown suggesting that M. leprae produces a post-translationally modified Hlp/LBP containing methyllysine residues. Methylation of the lysine residues, however, seems not to affect the adhesive properties of Hlp/LBP. Taken together, our observations reinforce the involvement of Hlp/LBP as an adhesin in mycobacterial infections and define its highly positive C-terminal region as the major adhesive domain of this protein.