In density cumulant functional theory (DCFT) the electronic energy is evaluated from the one-particle density matrix and two-particle density cumulant, circumventing the computation of the wavefunction. To achieve this, the one-particle density matrix is decomposed exactly into the mean-field (idempotent) and correlation components. While the latter can be entirely derived from the density cumulant, the former must be obtained by choosing a specific set of orbitals. In the original DCFT formulation [W. Kutzelnigg, J. Chem. Phys. 125, 171101 (2006)] the orbitals were determined by diagonalizing the effective Fock operator, which introduces partial orbital relaxation. Here we present a new orbital-optimized formulation of DCFT where the energy is variationally minimized with respect to orbital rotations. This introduces important energy contributions and significantly improves the description of the dynamic correlation. In addition, it greatly simplifies the computation of analytic gradients, for which expressions are also presented. We offer a perturbative analysis of the new orbital stationarity conditions and benchmark their performance for a variety of chemical systems.