Extreme stresses can be produced in nanoscale structures, a feature which has been used to realize enhanced materials properties, such as the high mobility of silicon in modern transistors. Here we show how nanoscale stress can be used to realize exceptionally low mechanical dissipation, when combined with “soft-clamping” — a form of phononic engineering. Specifically, using a non-uniform phononic crystal pattern, we colocalize the strain and flexural motion of a free-standing Si3N4 nanobeam. Ringdown measurements at room temperature reveal string-like modes with quality (Q) factors as high as 800 million and Q × frequency exceeding 1015 Hz. These results illustrate a promising route for engineering ultra-coherent nanomechanical devices.