Abstract: Compared with fractal image coding, wavelet based fractal image coding can cope with block artifacts and reduce match-searching time effectively. But using fractal coding in low frequency sub-band will lead to poor reconstructed image, and the match-searching time is still the main overhead for fractal image coding. So a fractal-searching-tree-based embedded wavelet image coding algorithm is proposed. The image is decomposed to multiple-level sub-bands by means of Haar wavelet. For the low frequency sub-band, the DPCM coding is applied directly. For the high frequency sub-bands, a self-adaptive approach is adopted to partition each sub-band into different range blocks according to the significance of sub-bands with different size. Then a fractal searching tree structure is constructed to determine the domain pool in which match-searching is carried out in a manner of zigzag scanning. Finally, the arithmetic coding method is employed to encode the fractal parameters obtained. Experimental results show that better reconstructed images are obtained as compared with those by other similar algorithms, and the PSNR is remarkably improved in medium and low bit rate. When the bit rate is less than 0.40bpp, the PSNR is promoted about 0.40~2.48dB averagely. Meanwhile the running time of the algorithm is also reduced.