Hydroxyapatite (HAP) is the major component of normal bone and teeth. The 43-residue protein statherin inhibits both the growth dynamics and nucleation of HAP in the environment of saliva. Despite their importance in hard-tissue formation and in pathological processes, there is little known of the statherin structure-function relationship and the molecular structure of the statherin-HAP interaction. In this work, we model statherin on HAP crystals with a multiscale Monte Carlo minimization structure prediction method. The protein structure is modeled according to solid state NMR constraints and includes two modified phosphoserine amino acids near the N-terminus. The HAP was modeled as a monoclinic crystal surface P2₁/b and an appropriate apatite forcefield was chosen. In the predicted model structure, residue Lys6 is close to the surface and has hydrogen bonds with HAP, and statherin is strongly bound in the acidic alpha-helical N-terminus in agreement with solid state NMR experiments.