Image segmentation is a crucial step in most computer vision tasks. We propose a new unsupervised fuzzy Bayesian image segmentation method using fuzzy Markov random fields (FMRFs). FRMF is known to provide improved segmentation results when compared to the "hard" MRF method. Typically, both hard and fuzzy MRF models have two groups of parameters to be estimated: the MRF parameters and class parameters for each pixel in the image. To this date, these two parameters are treated separately, and estimated in an alternating fashion. In this paper, we develop a new method to estimate the parameters defining the Markovian distribution of the measured data, while per-forming the data clustering simultaneously. This is made possible by defining estimates of the MRF parameters as functions of the class parameters resulting in a cost function that depends only on the class parameters of each pixel. We apply the conjugate gradient method (CGM) to search for the optimizer of the resulting non-linear cost function. We perform computer simulations to illustrate the proposed method and provide a comparison with some of the commonly used methods.