Texture segmentation is one of the early steps towards identifying surfaces and objects in an image. Textures considered here are defined in terms of primitives called tokens. In this paper we have developed a texture segmentation algorithm based on the Voronoi tessellation. The algorithm first builds the Voronoi tessellation of the tokens that make up the textured image. It then computes a feature vector for each Voronoi polygon. These feature vectors are used in a probabilistic relaxation labeling on the tokens, to identify the interior and the border regions of the textures. The algorithm has successfully segmented binary images containing textures whose primitives have identical second-order statistics and a number of gray level texture images.