An image encoding apparatus for encoding image data including a plurality of frames, determines an encoding block size of an encoding subject frame of the image data based on the obtained image data, encodes the obtained image data on an encoding block unit basis in accordance with the determined encoding block size, controls a code amount of the size-decided encoding block based on encoding information regarding the current size-decided encoding block and the encoding block encoded before the current encoding block, operates predetermined encoding information of the encoding subject frame based on the encoding information, and restricts the encoding block size to be determined, in accordance with the operated predetermined encoding information.