We use Cholesky decomposition of the density matrix in atomic orbital basis to define a new set of occupied molecular orbital coefficients. Analysis of the resulting orbitals (“Cholesky molecular orbitals”) demonstrates their localized character inherited from the sparsity of the density matrix. Comparison with the results of traditional iterative localization schemes shows minor differences with respect to a number of suitable measures of locality, particularly the scaling with system size of orbital pair domains used in local correlation methods. The Cholesky procedure for generating orthonormal localized orbitals is noniterative and may be made linear scaling. Although our present implementation scales cubically, the algorithm is significantly faster than any of the conventional localization schemes. In addition, since this approach does not require starting orbitals, it will be useful in local correlation treatments on top of diagonalization-free Hartree-Fock optimization algorithms.