Cells in tissues can be morphologically indistinguishable yet show molecular expression patterns that are remarkably heterogeneous. Here we describe an approach to comprehensively identify co-regulated, heterogeneously expressed genes among cells that otherwise appear identical. The technique, called stochastic profiling, involves repeated, random selection of very small cell populations via laser-capture microdissection followed by a customized single-cell amplification procedure and transcriptional profiling. Fluctuations in the resulting gene-expression measurements are then analyzed statistically to identify transcripts that are heterogeneously coexpressed. We stochastically profiled matrix-attached human epithelial cells in a three-dimensional culture model of mammary-acinar morphogenesis. Of 4,557 transcripts, we identified 547 genes with strong cell-to-cell expression differences. Clustering of this heterogeneous subset revealed several molecular 'programs' implicated in protein biosynthesis, oxidative-stress responses and NF-κB signaling, which we independently confirmed by RNA fluorescence in situ hybridization. Thus, stochastic profiling can reveal single-cell heterogeneities without the need to measure expression in individual cells.