It is an object of the present invention to provide an image encoding apparatus, an image encoding method, and an image encoding program, which can homogenize image quality of an image as a whole without lowering encoding efficiency, being operable at high speed, and reduce the size of circuit scale by performing macroblock shuffling without changing slice structure. Provided is an image encoding apparatus, including: a shuffling portion which collects and shuffles a plurality of macroblocks constituting image data from respective positions within an image; an encoding portion which performs space-frequency transform and entropy encoding on the plurality of macroblocks collected and shuffled by the shuffling portion, as a base unit; and a rate control portion which controls the encoding portion to adjust the rate of the plurality of macroblocks after the encoding.