A video encoding method and apparatus performing intra-frame prediction in units of a sub-block determined by any one of two or more block sizes is provided. The method includes generating a prediction image in each of a plurality of intra-frame prediction modes in units of the sub-block determined by each block size, calculating a first evaluation value on the basis of the difference images between an original image and the prediction images in the intra-frame prediction modes for the sub-blocks determined by each block size, accumulating values indicating frequency characteristics of the original image for the sub-blocks determined by each block size in units of a macroblock to obtain a second evaluation value, and selecting one of the two or more block sizes on the basis of the first evaluation values and the second evaluation values.