Ubiquitin is an important cellular signal that targets proteins for degradation or regulates their functions. The previously identified BMSC-UbP protein derived from bone marrow stromal cells contains a ubiquitin-associated (UBA) domain at the C terminus that has been implicated in linking cellular processes and the ubiquitin system. Here, we report the solution NMR structure of the UBA domain of human BMSC-UbP protein and its complex with ubiquitin. The structure determination was facilitated by using a solubility-enhancement tag (SET) GB1, immunoglobulin G binding domain 1 of Streptococcal protein G. The results show that BMSC-UbP UBA domain is primarily comprised of three alpha-helices with a hydrophobic patch defined by residues within the C terminus of helix-1, loop-1, and helix-3. The M-G-I motif is similar to the M/L-G-F/Y motifs conserved in most UBA domains. Chemical shift perturbation study revealed that the UBA domain binds with the conserved five-stranded beta-sheet of ubiquitin via hydrophobic interactions with the dissociation constant (KD) of approximately 17 microM. The structural model of BMSC-UbP UBA domain complexed with ubiquitin was constructed by chemical shift mapping combined with the program HADDOCK, which is in agreement with the result from mutagenesis studies. In the complex structure, three residues (Met76, Ile78, and Leu99) of BMSC-UbP UBA form a trident anchoring the domain to the hydrophobic concave surface of ubiquitin defined by residues Leu8, Ile44, His68, and Val70. This complex structure may provide clues for BMSC-UbP functions and structural insights into the UBA domains of other ubiquitin-associated proteins that share high sequence homology with BMSC-UbP UBA domain.