The rational design of hydrogen evolution reaction (HER) electrocatalysts which are competitive with platinum is an outstanding challenge to make power-to-gas technologies economically viable. Here, we introduce the delafossites PdCrO$_2$, PdCoO$_2$ and PtCoO$_2$ as a new family of electrocatalysts for the HER in acidic media. We show that in PdCoO$_2$ the inherently strained Pd metal sublattice acts as a pseudomorphic template for the growth of a strained (by +2.3%) Pd rich capping layer under reductive conditions. The surface modification continuously improves the electrocatalytic activity by simultaneously increasing the exchange current density j$_0$ from 2 to 5 mA/cm$^2_{geo}$ and by reducing the Tafel slope down to 38 mV/decade, leading to overpotentials $eta_{10}$ < 15 mV for 10 mA/cm$^2_{geo}$, superior to bulk platinum. The greatly improved activity is attributed to the in-situ stabilization of a $beta$-palladium hydride phase with drastically enhanced surface catalytic properties with respect to pure or nanostructured palladium. These findings illustrate how operando induced electrodissolution can be used as a top-down design concept for rational surface and property engineering through the strain-stabilized formation of catalytically active phases.