A fast algorithm for fractal image coding based on a single kick-out condition and the zero contrast prediction is proposed in this paper. The single kick-out condition can avoid a large number of range-domain block matches when finding the best matched domain block. An efficient method for zero contrast prediction is also proposed, which can determine whether the contrast factor for a domain block is zero or not, and compute the corresponding difference between the range block and the transformed domain block efficiently and exactly. The proposed algorithm can achieve the same reconstructed image quality as the exhaustive search, and can greatly reduce the required computation or runtime. In addition, this algorithm does not need any pre-processing step or additional memory for its implementation, and can combine with other fast fractal algorithms to further improve the speed. Experimental results show that the runtime is reduced by about 50% of that of the exhaustive search method. When combined with the DCT Inner Product algorithm, the required runtime for the algorithm can be further reduced by about 50%. The proposed algorithm was also compared to two other fast fractal algorithms. Experimental results also show that our algorithm achieves a better efficiency and requires a much smaller amount of memory for implementation.