Accurate multispectral image segmentation is essential in remote sensing research. Traditional fuzzy clustering algorithms used to segment multispectral images have several disadvantages, including: (1) they usually only consider the pixels’ grayscale information and ignore the interaction between pixels; and, (2) they are sensitive to noise and outliers. To overcome these constraints, this study proposes a multispectral image segmentation algorithm based on fuzzy clustering combined with the Tsallis entropy and Gaussian mixture model. The algorithm uses the fuzzy Tsallis entropy as regularization item for fuzzy C-means (FCM) and improves dissimilarity measure using the negative logarithm of the Gaussian Mixture Model (GMM). The Hidden Markov Random Field (HMRF) is introduced to define prior probability of neighborhood relationship, which is used as weights of the Gaussian components. The Lagrange multiplier method is used to solve the segmentation model. To evaluate the proposed segmentation algorithm, simulated and real multispectral images were segmented using the proposed algorithm and two other algorithms for comparison (i.e., Tsallis Fuzzy C-means (TFCM), Kullback–Leibler Gaussian Fuzzy C-means (KLG-FCM)). The study found that the modified algorithm can accelerate the convergence speed, reduce the effect of noise and outliers, and accurately segment simulated images with small gray level differences with an overall accuracy of more than 98.2%. Therefore, the algorithm can be used as a feasible and effective alternative in multispectral image segmentation, particularly for those with small color differences.