Phenotypic heterogeneity in clonal bacterial batch cultures has been shown for a range of bacterial systems; however, the molecular origins of such heterogeneity and its magnitude are not well understood. Under conditions of extreme low-nitrogen stress in the model diazotroph Klebsiella oxytoca, we found remarkably high heterogeneity of nifHDK gene expression, which codes for the structural genes of nitrogenase, one key enzyme of the global nitrogen cycle. This heterogeneity limited the bulk observed nitrogen-fixing capacity of the population. Using dual-probe, single-cell RNA fluorescent in situ hybridization, we correlated nifHDK expression with that of nifLA and glnK-amtB, which code for the main upstream regulatory components. Through stochastic transcription models and mutual information analysis, we revealed likely molecular origins for heterogeneity in nitrogenase expression. In the wild type and regulatory variants, we found that nifHDK transcription was inherently bursty, but we established that noise propagation through signaling was also significant. The regulatory gene glnK had the highest discernible effect on nifHDK variance, while noise from factors outside the regulatory pathway were negligible. Understanding the basis of inherent heterogeneity of nitrogenase expression and its origins can inform biotechnology strategies seeking to enhance biological nitrogen fixation. Finally, we speculate on potential benefits of diazotrophic heterogeneity in natural soil environments.