In this paper, a new fast classification strategy is proposed for fractal image compression with quadtree partitioning technique. The scheme significantly reduces the number of mean square error (MSE) computations during encoding of images. Performance in terms of compression ratios, compression time and PSNR of the fractal image compression with existing and proposed classification strategy are compared. Both techniques use quadtree partitioning scheme. The proposed classification strategy reduces the compression time significantly of the fractal image compression technique maintaining compression ratio and PSNR almost same with its counterpart.