An image encoding device adapted to segment an image into blocks and encode the image in units of blocks resulting from segmenting the image is provided. A block segmentation unit (101) recursively segments the image into rectangles of a predetermined size to generate a block subject to encoding. A bitstream generation unit (105) encodes block segmentation information of the block subject to encoding. The block segmentation unit (101) includes: a quartering unit that quarters a target block in recursive segmentation in a horizontal direction and a vertical direction to generate four blocks; and a halving unit that halves a target block in recursive segmentation in a horizontal or vertical direction to generate two blocks. When previous recursive segmentation is halving, the halving unit prohibits a target block subject to current recursive segmentation from being segmented in the same direction as a direction in which the block was segmented in the previous recursive segmentation.