Localized molecular orbitals (LMOs) are much more compact representations of electronic degrees of freedom than canonical molecular orbitals (CMOs) The most compact representation is provided by nonorthogonal localized molecular orbitals (NOLMOs), which are linearly independent but are not orthogonal Both LMOs and NOLMOs are thus useful for linear-scaling calculations of electronic structures for large systems Recently, NOLMOs have been successfully applied to linear-scaling calculations with density functional theory (DFT) and to reformulating time-dependent density functional theory (TDDFT) for calculations of excited states and spectroscopy However, a challenge remains as NOLMO construction from CMOs is still inefficient for large systems In this work, we develop an efficient method to accelerate the NOLMO construction by using predefined centroids of the NOLMO and thereby removing the nonlinear equality constraints in the original method (J Chem. Phys 2004, 120, 9458 and J Chem Phys. 2000, 112, 4). Thus, NOLMO construction becomes an unconstrained optimization Its efficiency is demonstrated for the selected saturated and conjugated molecules. Our method for fast NOLMO construction should lead to efficient DFT and NOLMO-TDDFT applications to large systems