An efficient synthetic aperture radar (SAR) image segmentation approach using a Markov random field (MRF) model with edge penalties and an adaptive weighting parameter is proposed. The edge penalty and the adaptive weighting parameter are introduced into the energy function of MRF segmentation model. As a result, the edge fuzzy is reduced with the introduction of edge penalty. The adaptive weighting parameter can adjust adaptively the weights of the data modeling factor in the energy function according to the stages of iteration and the heterogeneity of local scenes, which is in favor to get smoother results for homogeneous regions and preserve edges and important image details for heterogeneous regions. An efficient optimization algorithm called heterogeneous point tracking algorithm is presented in terms of the characteristics of the energy function. Experiments with simulated data and real SAR images show that the proposed algorithm improves the segmentation accuracy and reduces the running time.