An intra prediction mode determination apparatus includes prediction units which perform intra prediction on a block of a first block size in an image including at least one block, a first determination unit which determines one of the prediction units used to perform the intra prediction on the block of a processing target, and a second determination unit which determines an intra prediction mode for the block of the processing target from among candidates of an intra prediction mode which are used by the determined prediction unit in accordance with a result of the intra prediction performed by the determined prediction unit. When the block of the processing target includes a block of a second block size which is larger than the first block size, the prediction unit performs intra prediction on blocks of the first block size obtained by dividing the block of the second block size.