Measuring multiple omics profiles from the same single cell opens up the opportunity to decode molecular regulation that underlies intercellular heterogeneity in development and disease. Here, we present co-sequencing of microRNAs and mRNAs in the same single cell using a half-cell genomics approach. This method demonstrates good robustness (~95% success rate) and reproducibility (R2 = 0.93 for both microRNAs and mRNAs), yielding paired half-cell microRNA and mRNA profiles, which we can independently validate. By linking the level of microRNAs to the expression of predicted target mRNAs across 19 single cells that are phenotypically identical, we observe that the predicted targets are significantly anti-correlated with the variation of abundantly expressed microRNAs. This suggests that microRNA expression variability alone may lead to non-genetic cell-to-cell heterogeneity. Genome-scale analysis of paired microRNA-mRNA co-profiles further allows us to derive and validate regulatory relationships of cellular pathways controlling microRNA expression and intercellular variability.