A moving image encoding device includes determining whether an orthogonal transformation coefficient to which orthogonal transformation processing has been executed is equal to or less than a threshold determined from a quantization step used for quantization processing, and first calculating an encoding error from a first coefficient determined to be the threshold or less among the orthogonal transformation coefficients and the number of second coefficients determined to be larger than the threshold, and estimating, from the number of the second coefficients, an information amount generated when variable length encoding processing is executed to the orthogonal transformation coefficient after execution of the quantization processing, and second calculating an encoding cost from the encoding error and the information amount.