This study examines the lossless compression of an original JPEG bitstream such that spare space is reserved to embed secret data in a file header. After an original image is transformed using discrete cosine transform (DCT), the nonzero DCT coefficients at high frequencies are relatively sparse and their absolute values are small. To improve encoding efficiency, we propose a segment encoding algorithm that defines a high frequency in DCT blocks as the termination point and recodes coefficients separately. The coefficients above this point are encoded in the proposed Rxy code, and the coefficients below it are encoded in JPEG code. Then, to further preserve the embedding capacity’s (EC) robustness to different quality factors, we cluster blocks into large 32  ×  32 blocks and record special block indexes that are not suitable for Rxy encoding in appended data. Hence, space is reserved for inserting secret data and appended data after the comment marker in a file header. A receiver can obtain the termination point through data analysis, extract additional data, and recover the original JPEG image in a lossless manner. Encoding redundancy is substantially reduced such that a large EC can be achieved with no file expansion. Moreover, only coefficients at high frequencies are recoded; hence, concealment is computationally simple. Experimental results demonstrate that the proposed method has a larger EC than state-of-the-art methods.