Color image segmentation can be defined as dividing a color image into several disjoint, homogeneous, and meaningful regions based on the color information. This paper proposes an efficient segmentation algorithm for color images based on neutrosophic adaptive mean shift (NAMS) clustering. Firstly, an image is transformed in neutrosophic set and interpreted by three subsets: true, indeterminate, and false memberships. Then a filter is designed using indeterminacy membership value, and neighbors’ features are employed to alleviate indeterminacy degree of image. A new mean shift clustering, improved by neutrosophic set, is employed to categorize the pixels into different groups whose bandwidth is determined by the indeterminacy values adaptively. At last, the segmentation is achieved using the clustering results. Various experiments have been conducted to verify the performance of the proposed approach. A published method was then employed to take comparison with the NAMS on clean, low contrast, and noisy images, respectively. The results demonstrate the NAMS method achieves better performances on both clean image and low contrast and noisy images.