Single-cell spatial transcriptomics reveals how cells organize in healthy and diseased tissues. From these data, tissue segmentation analysis defines discrete compartments that organize cells into functional multicellular units. Existing methods for automated tissue segmentation rely on spatial smoothing to define spatially coherent regions but often blur the boundaries between adjacent tissue compartments. We describe Tessera, an algorithm that approaches tissue segmentation through a novel approach, dividing the tissue into small multicellular tiles whose edges track with natural tissue boundaries. Tessera achieves this by incorporating successful tools from edge-preserving smoothing, topological data analysis, and morphology-aware agglomerative spatial clustering. We show that Tessera identifies a range of known anatomical structures, in healthy mouse brain and human lymph nodes, and novel disease-associated niches, in human brain and in lung cancer. Tessera is a general-purpose tool that returns spatially coherent spatial structures with accurate boundaries across a range of spatial transcriptomics and proteomics technologies.