Orbital physics plays a significant role for a vast number of important phenomena in complex condensed-matter systems, including high-temperature superconductivity and unconventional magnetism. In contrast, phenomena in superfluids-in particular in ultracold quantum gases-are typically well described by the lowest orbital and a real order parameter. Here, we report on the observation of a multi-orbital superfluid phase with a complex order parameter in binary spin mixtures. In this unconventional superfluid, the local phase angle of the complex order parameter is continuously twisted between neighbouring lattice sites. The nature of this twisted superfluid quantum phase is an interaction-induced admixture of the p-orbital contributions favoured by the graphene-like band structure of the hexagonal optical lattice used in the experiment. We observe a second-order quantum phase transition between the normal superfluid and the twisted superfluid phase, which is accompanied by a symmetry breaking in momentum space. The experimental results are consistent with calculated phase diagrams and reveal fundamentally new aspects of orbital superfluidity in quantum gas mixtures. Our studies might bridge the gap between conventional superfluidity and complex phenomena of orbital physics.