In this paper, we propose an approach based on fractal dimension to automatically locate address blocks in postal envelopes. First, the fractal dimension of each pixel of a postal envelope image is computed using the 2D variation procedure. The K-means clustering technique is then used to label pixels as background, noise and semantic objects like stamps, postmarks, and address blocks. A database composed of 200 postal envelope images, with no fixed position for the address block, postmark and stamp is used to evaluate the efficiency of the proposed approach. For each envelope image, the ideal result (ground-truth segmentation) regarding each class has been generated. The comparison between the ground-truth segmentation and the results obtained through the proposed methodology is carried out pixel by pixel. Experiments showed significant and promising results. By using the 2D variation procedure for three ranges of neighbor window sizes (r = {3; 5}, r = {3; 5; 7}, and r = {3; 5; 7; 9}), the proposed approach reached a success rate over than 90% on average.