We present a novel method for automated identification of putative cell types from single-cell RNA-seq (scRNA-seq) data. By iteratively applying a machine learning approach to an initial clustering of gene expression profiles of a given set of cells, we simultaneously identify distinct cell groups and a weighted list of feature genes for each group. The feature genes, which are differentially expressed in the particular cell group, jointly discriminate the given cell group from other cells. Each such group of cells corresponds to a putative cell type or state, characterised by the feature genes as markers. To benchmark this approach, we use expert-annotated scRNA-seq datasets from a range of experiments, as well as comparing to existing cell annotation methods, which are all based on a pre-existing reference. We show that our method automatically identifies the “ground truth” cell assignments with high accuracy. Moreover, our method, “Single Cell Clustering Assessment Framework” (SCCAF) predicts new putative biologically meaningful cell-states in published data on haematopoiesis and the human cortex. SCCAF is available as an open-source software package on GitHub (https://github.com/SCCAF/sccaf) and as a Python package index and has also been implemented as a Galaxy tool in the Human Cell Atlas.