The heat engine, a machine that extracts useful work from thermal sources, is one of the basic theoretical constructs and fundamental applications of classical thermodynamics. The classical description of a heat engine makes no allowance for coherence in its microscopic degrees of freedom; by contrast, a quantum heat engine might possess some degree of coherence between its internal states. Recently, it was predicted that, in the limit of small action with respect to ℏ, the presence coherence would result in the thermodynamic equivalence of different quantum heat engine types; moreover it would allow for a greater power output than a classical heat engine using the same resources. Here we implement two types of quantum heat engines by use of an ensemble of nitrogen-vacancy centers in diamond, and experimentally demonstrate these quantum thermodynamic signatures for the first time. In particular, we measure output powers that beat the stochastic bound by four standard deviations, and show that the power decreases below the bound as coherence is reduced.