Compositions, methods and kits are disclosed for high-sensitivity single molecule digital counting by the stochastic labeling of a collection of identical molecules by attachment of a diverse set of labels. Each copy of a molecule randomly chooses from a non-depleting reservoir of diverse labels. Detection may be by a variety of methods including hybridization based or sequencing. Molecules that would otherwise be identical in information content can be labeled to create a separately detectable product that is unique or approximately unique in a collection. This stochastic transformation relaxes the problem of counting molecules from one of locating and identifying identical molecules to a series of binary digital questions detecting whether preprogrammed labels are present. The methods may be used, for example, to estimate the number of separate molecules of a given type or types within a sample.