We demonstrate that the simultaneous substitution of calcium and aluminum for strontium and iron in strontium hexaferrite results in a significant increase of coercivity up to a record high of 21.3 kOe. We propose that the effect is originated from a crystal structure distortion causing an increase of the magnetocrystalline anisotropy.