A moving image coding device 10 includes: a cost determination unit 12 that determines, as a cost relating to a block to be coded, a minimum cost among appraisal costs relating to determined candidates for a motion vector; a storage unit 13 that stores, as coding information relating to the block to be coded, a candidate for the motion vector corresponding to the determined cost; and an update unit 14 that updates, to coding information relating to the block to be coded, the cost of which is smaller than the sum total of costs relating to blocks included in the block to be coded, the coding information relating to the included blocks and stored in the storage unit 13.