Energy conversion of heat into work at the quantum level is modeled by quantum heat machines (QHMs) generally assumed to operate at weak coupling to the baths. This supposition is grounded in the separability principle between systems and allows the derivation of the evolution equation. In the weak coupling regime, the machine's output is limited by the coupling strength, restricting their application. Seeking to overcome this limitation, we analyze QHMs in the virtually unexplored strong coupling regime here, where separability, as well as other standard thermodynamic assumptions, may no longer hold. We show that strongly coupled QHMs may be as efficient as their weakly coupled counterparts. In addition, we find a novel turnover behavior where their output saturates and disappears in the limit of ultrastrong coupling.