This paper introduces the use of complex Fermi orbital descriptors (FODs) in the Fermi-Löwdin self-interaction-corrected density functional theory (FLOSIC). With complex FODs, the Fermi-Löwdin orbitals (FLOs) that are used to evaluate the SIC correction to the total energy become complex. Complex FLO-SIC (cFLOSIC) calculations based on the local spin density approximation produce total energies that are generally lower than the corresponding energies found with FLOSIC restricted to real orbitals (rFLOSIC). The cFLOSIC results are qualitatively similar to earlier Perdew-Zunger SIC (PZ-SIC) calculations using complex orbitals [J. Chem. Phys. 80, 1972 (1984); Phys. Rev. A 84, 050501(R) (2011); and J. Chem. Phys. 137, 124102 (2012)]. The energy lowering stems from the exchange-correlation part of the self-interaction correction. The Hartree part of the correction is more negative in rFLOSIC. The energy difference between real and complex solutions is greater for more strongly hybridized FLOs in atoms and for FLOs corresponding to double and triple bonds in molecules. The case of N2 is examined in detail to show the differences between the real and complex FLOs. We show that the complex triple-bond orbitals are simple, and physically appealing combinations of π and σg orbitals that have not been discussed before. Consideration of complex FODs, and resulting unitary transformations, underscores the fact that FLO centroids are not necessarily good guesses for FOD positions in a FLOSIC calculation.