Data hiding technology plays an important role in many areas related to people’s life, such as military and medical images. However, it is difficult to obtain high embedding capacity in compressed images, and it may cause obvious image distortion. Also, the target image’s file size should be controlled, as a significant increase in file size may cause the interceptor’s attention. In the field of data hiding, many people have proposed feasible solutions. However, considering the visual quality and embedding rate of images, more improvements are needed. In this paper, histogram shift is used to realize data hiding of JPEG images. The secret message bits are embedded in the high-frequency coefficients to ensure a higher embedding rate, and the high-frequency coefficients are obtained by histogram distribution. The optimal threshold is used to select a Discrete Cosine Transform (DCT) coefficient sub-block that is suitable to embed the secret message, and further improve the visual quality of the target image. Experiments show that our solution is significantly better than the most advanced technology in terms of embedding rate and visual quality.