Molybdenum borides were studied theoretically using first-principles calculations, parameterized lattice model, and global optimization techniques to determine stable crystal structures. Our calculations reveal the structures of known Mo-B phases, attaining close agreement with experiment. Following our developed lattice model, we describe in detail the crystal structure of boron-rich MoBx phases with 3 ≤ x ≤ 9 as the hexagonal P63/mmc-MoB3 structure with Mo atoms partially replaced by triangular boron units. The most energetically stable arrangement of these B3 units corresponds to their uniform distribution in the bulk, which leads to the formation of a disordered nonstoichiometric phase, with ordering arising at compositions close to x = 5 because of a strong repulsive interaction between neighboring B3 units. The most energetically favorable structures of MoBx correspond to the compositions 4 ≲ x ≤ 5, with MoB5 being the boron-richest stable phase. The estimated hardness of MoB5 is 37-39 GPa, suggesting that the boron-rich phases are potentially superhard.