Fuzzy C-Means (FCM) algorithm has been widely used in remote sensed image segmentation. However, it has two main defects: (1) its sensitiveness to noise outliers, and other imaging artifacts; (2) the number of clusters needed to be set previously. In order to overcome these problems, in this paper, we incorporate the wavelet energy histograms (WEHs) and Markov random field models (MRFs) into the fuzzy clustering procedure and present a novel image segmentation method. WEHs serve the determination of cluster centers and MRFs play a role of modelling spatial information. First of all, the peaks of wavelet histogram are exploited to find the initial cluster centers. Then, a fuzzy clustering procedure with MRFs is performed on each band separately. Finally, the fused label of the clustering result from each band is used as the final segmentation result. The superiority of the proposed method is demonstrated by comparing it with the some well-known methods of FCM, FLICM, HMRF-FCM, and AHFCM.