Decisively delineating cell identities from uni- and multimodal single-cell datasets is complicated by diverse modalities, clustering methods, and reference atlases. We describe scTriangulate, a computational framework to mix-and-match multiple clustering results, modalities, associated algorithms, and resolutions to achieve an optimal solution. Rather than ensemble approaches which select the "consensus", scTriangulate picks the most stable solution through coalitional iteration. When evaluated on diverse multimodal technologies, scTriangulate outperforms alternative approaches to identify high-confidence cell-populations and modality-specific subtypes. Unlike existing integration strategies that rely on modality-specific joint embedding or geometric graphs, scTriangulate makes no assumption about the distributions of raw underlying values. As a result, this approach can solve unprecedented integration challenges, including the ability to automate reference cell-atlas construction, resolve clonal architecture within molecularly defined cell-populations and subdivide clusters to discover splicing-defined disease subtypes. scTriangulate is a flexible strategy for unified integration of single-cell or multimodal clustering solutions, from nearly unlimited sources.