This paper presents a new approach for unsupervised segmentation of histopathological tissue images. This approach has two main contributions. First, it introduces a new set of high-level texture features to represent the prior knowledge of spatial organization of the tissue components. These texture features are defined on the tissue components, which are approximately represented by tissue objects, and quantify the frequency of two component types being cooccurred in a particular spatial relationship. As they are defined on components, rather than on image pixels, these object cooccurrence features are expected to be less vulnerable to noise and variations that are typically observed at the pixel level of tissue images. Second, it proposes to obtain multiple segmentations by multilevel partitioning of a graph constructed on the tissue objects and combine them by an ensemble function. This multilevel graph partitioning algorithm introduces randomization in graph construction and refinements in its multilevel scheme to increase diversity of individual segmentations, and thus, improve the final result. The experiments on 200 colon tissue images reveal that the proposed approach-the object cooccurrence features together with the multilevel segmentation algorithm-is effective to obtain high-quality results. The experiments also show that it improves the segmentation results compared to the previous approaches.