Quantum interference is at the heart of what sets the quantum and classical worlds apart. We demonstrate that quantum interference effects involving a many-body working medium is responsible for genuinely nonclassical features in the performance of a quantum heat engine. The features with which quantum interference manifests itself in the work output of the engine depends strongly on the extensive nature of the working medium. While identifying the class of work substances that optimize the performance of the engine, our results shed light on the optimal size of such media of quantum workers to maximize the work output and efficiency of quantum energy machines.