Tissues are organized in cellular niches, the composition and interactions of which can be investigated using spatial omics technologies. However, systematic analyses of tissue composition are challenged by the scale and diversity of the data. Here we present CellCharter, an algorithmic framework to identify, characterize, and compare cellular niches in spatially resolved datasets. CellCharter outperformed existing approaches and effectively identified cellular niches across datasets generated using different technologies, and comprising hundreds of samples and millions of cells. In multiple human lung cancer cohorts, CellCharter uncovered a cellular niche composed of tumor-associated neutrophil and cancer cells expressing markers of hypoxia and cell migration. This cancer cell state was spatially segregated from more proliferative tumor cell clusters and was associated with tumor-associated neutrophil infiltration and poor prognosis in independent patient cohorts. Overall, CellCharter enables systematic analyses across data types and technologies to decode the link between spatial tissue architectures and cell plasticity.