A new high-pressure phase of RhB has been predicted using a newly developed particle swarm optimization algorithm based on first-principles calculations. The new phase belongs to the orthorhombic Pnma space group (FeB type); it transforms from hexagonal RhB (anti-NiAs type) when the pressure exceeds 22 GPa. The high-pressure phase is both mechanically and dynamically stable, as verified by the calculations of its elastic stiffness constants and phonon dispersion. Further calculations predicate this high-pressure phase to be semimetallic, with excellent ductility (B/G = 3.56) and high Vickers hardness (25 GPa).