Skyrmions are localized, topologically non-trivial spin structures which have raised high hopes for future spintronic applications. A key issue is skyrmion stability with respect to annihilation into the ferromagnetic state. Energy barriers for this collapse have been calculated taking only nearest neighbor exchange interactions into account. Here, we demonstrate that exchange frustration can greatly enhance skyrmion stability. We focus on the prototypical film system Pd/Fe/Ir(111) and use an atomistic spin model parametrized from first-principles calculations. We show that energy barriers and critical fields of skyrmion collapse as well as skyrmion lifetimes are drastically enhanced due to frustrated exchange and that antiskyrmions are metastable. In contrast an effective nearest-neighbor exchange model can only account for equilibrium properties of skyrmions such as their magnetic field dependent profile or the zero temperature phase diagram. Our work shows that frustration of long range exchange interactions – a typical feature in itinerant electron magnets – is a route towards enhanced skyrmion stability even in systems with a ferromagnetic ground state.