To provide a moving image encoding device performing optimal inter-predictive coding even for any image to be encoded in the case of using a rate distortion evaluation value using a Lagrange multiplier to make encoding, and obtaining satisfactory image quality by improving encoding efficiency.

A Lagrange multiplier λ is changed to apply temporary encoding to the image to be encoded at least one time or more to obtain a relation to quantization coefficient, the Lagrange multiplier λ is optimized, and this value is used to make actual encoding. Consequently, optimal encoding for the image to be encoded is made and high encoding efficiency and satisfactory image quality are obtained.