We formulate the Kohn-Sham density functional theory (KS-DFT) as a statistical theory in which the electron density is determined from an average of correlated stochastic densities in a trace formula. The key idea is that it is sufficient to converge the total energy per electron to within a predefined statistical error in order to obtain reliable estimates of the electronic band structure, the forces on nuclei, the density and its moments, etc. The fluctuations in the total energy per electron are guaranteed to decay to zero as the system size increases. This facilitates “self-averaging” which leads to the first ever report of sublinear scaling KS-DFT electronic structure. The approach sidesteps calculation of the density matrix and thus, is insensitive to its evasive sparseness, as demonstrated here for silicon nanocrystals. The formalism is not only appealing in terms of its promise to far push the limits of application of KS-DFT, but also represents a cognitive change in the way we think of electronic structure calculations as this stochastic theory seamlessly converges to the thermodynamic limit.