Using the evolutionary methodology for crystal structure prediction, we have predicted the orthorhombic Cmcm and Pnma phases for ScB 4. The earlier proposed CrB 4-, FeB 4-, MnB 4-, and ReP 4-type structures for ScB 4 are excluded. It is first discovered that the Cmcm phase transforms to the Pnma phase at about 18 GPa. Moreover, both phases are dynamically and mechanically stable. The large bulk modulus, shear modulus, and Young’s modulus of the two phases make it an optimistic low compressible material. Moreover, the strong covalent bonding nature of ScB 4 is confirmed by the ELF analysis. The strong covalent bonding contributes greatly to its stability.