Mail sorting automation is yet a partially solved challenge. Due to no fixed positions of the semantic information in envelope images, part of this challenge is the automatic location of address blocks. In this paper we approach this problem by proposing a new postal envelope segmentation method based on 2-D histogram clustering and watershed transform. Segmentation task consists in detecting the 2-D histogram modes associated with homogeneous regions in envelope. A new filter used for 2-D histogram calculation is proposed. The homogeneous modes in 2-D histogram are segmented through the morphological watershed transform. Our approach is applied to complex postal envelopes. Very little a priori knowledge of the envelope images is required. The advantages of this approach will be described and illustrated with tests carried out on 300 different images where there are no fixed position for the handwritten address block, postmarks and stamps. A groundtruth strategy is employed to evaluate the accuracy of segmentation.