Heterogeneity between individual cells is a common feature of dynamic cellular processes, including signaling, transcription, and cell fate; yet the overall tissue level physiological phenotype needs to be carefully controlled to avoid fluctuations. Here we show that in the NF-kappaB signaling system, the precise timing of a dual-delayed negative feedback motif [involving stochastic transcription of inhibitor kappaB (IkappaB)-alpha and -epsilon] is optimized to induce heterogeneous timing of NF-kappaB oscillations between individual cells. We suggest that this dual-delayed negative feedback motif enables NF-kappaB signaling to generate robust single cell oscillations by reducing sensitivity to key parameter perturbations. Simultaneously, enhanced cell heterogeneity may represent a mechanism that controls the overall coordination and stability of cell population responses by decreasing temporal fluctuations of paracrine signaling. It has often been thought that dynamic biological systems may have evolved to maximize robustness through cell-to-cell coordination and homogeneity. Our analyses suggest in contrast, that this cellular variation might be advantageous and subject to evolutionary selection. Alternative types of therapy could perhaps be designed to modulate this cellular heterogeneity.