Many components and structures are exposed to very high number of cycles and challenging environmental conditions during operation. This study contributes to a better understanding of the very high cycle fatigue (VHCF) properties of high-strength steel X5CrNiCuNb16-4 at room temperature (RT) and 350 °C. For this purpose, conventional specimens and thin-walled structures are extensively examined with novel high-frequency fatigue testing techniques at elevated temperature. Tests with unnotched specimens at 350 °C show a 21.7% reduction in fatigue strength for 107 cycles and a different failure mechanism compared to RT. In contrast, no temperature influence is observed for mildly notched specimens and even a higher local fatigue strength is found for sharply notched specimens at 350 °C. The decrease in fatigue strength for 109 cycles is more pronounced at 350 °C (−10%) than at RT (−5%), and it is proven that notched specimens adequately represent the VHCF behaviour of structures. The transferability of specimen results to components and structures is given great attention. A new proposal for the VHCF strength assessment of structures with high stress gradients is presented, which is based on specimen results, an extended material-mechanical support factor and a VHCF reduction factor. The prediction model gives conservative fatigue strength estimates for 109 cycles with a maximum deviation of 5.8%. This demonstrates that even complex shaped structures can be successfully evaluated with suitable specimens and methods.