Aiming at the problems of strong speckle noise in sidescan sonar images and object segmentation difficulty, a segmentation algorithm based on spaceconstrained fast fuzzy Cmeans clustering (SCFFCM) and Markov random field (MRF) is proposed in this paper. Firstly, the strong speckle noise in sonar images is removed in nonsubsampled contourlet transform (NSCT) domain based on Bayesian maximum posteriori probability theory. Secondly, SCFFCM algorithm is proposed to accelerate the segmentation speed and give a good initial segmentation. Thirdly, the constrained field of MRF model is calculated from the initial segmentation, the combined weights of fuzzy clustering and Markov random field are adaptively updated according to the image gray fluctuations within the neighborhood; then the joint field of FCM fuzzy field and MRF constrained field is solved, and the segmentation result is obtained based on the maximum probability criterion. Finally, considering the noise points and ‘hole’ phenomenon in the segmentation result, a postprocessing method based on morphology is adopted to remove the isolated noise points and complete the ‘hole’ filling. Segmentation experiments on simulated and actual sidescan sonar images were conducted. Experiment results show that the proposed algorithm has stronger antinoise capability, higher segmentation precision and faster calculation speed compared with FCM and some other improved FCM algorithms.