The region segmentation of the pap-smear image is known to be a difficult and important part in the automatic image recognition system. Both the pixel based methods(thresholding) and the region based methods(split and merge, region growing and edge detection) are widely used for segmentation of the nucleus, cytoplasm and background in the pap-smear images. The pixel based methods are relatively fast, but not accurate, while the region based methods are accurate, but slow. This paper proposes a multistage segmentation strategy which uses thresholding and incremental color clustering methods to reduce computation time while not sacrificing accuracy. Proposed method consists of three stages. The first stage uses global thresholding method to search nucleus blob position, and the second stage employs incremental color clustering with color information. The final stage segments unsuitable nuclei using thresholding method after calculating suitability for each extracted nucleus blob. The proposed segmentation method is tested under various error measures. The experimental results showed that each stage of the proposed method reduced specific error measures: The second stage reduced false negative error and the third stage false positive error.