Ab initio no-core configuration interaction (NCCI) calculations for the nuclear many-body problem have traditionally relied upon an antisymmetrized product (Slater determinant) basis built from harmonic oscillator orbitals. The accuracy of such calculations is limited by the finite dimensions which are computationally feasible for the truncated many-body space. We therefore seek to improve the accuracy obtained for a given basis size by optimizing the choice of single-particle orbitals. Natural orbitals, which diagonalize the one-body density matrix, provide a basis which maximizes the occupation of low-lying orbitals, thus accelerating convergence in a configuration-interaction basis, while also possibly providing physical insight into the single-particle structure of the many-body wave function. We describe the implementation of natural orbitals in the NCCI framework, and examine the nature of the natural orbitals thus obtained, the properties of the resulting many-body wave functions, and the convergence of observables. After taking 3He as an illustrative testbed, we explore aspects of NCCI calculations with natural orbitals for the ground state of the p-shell neutron halo nucleus 6He.