Engineered micro- and nanomechanical resonators with ultra-low dissipation constitute a promising platform for various quantum technologies and foundational research. Traditionally, the improvement of the resonator’s performance through nanomechanical structural engineering has been driven by human intuition and insight. Such an approach is inefficient and leaves aside a plethora of unexplored mechanical designs that potentially achieve better performance. Here, we use a computer-aided inverse design approach known as topology optimization to structurally design mechanical resonators with optimized performance of the fundamental mechanical mode. Using the outcomes of this approach, we fabricate and characterize ultra-coherent nanomechanical resonators with, to the best of our knowledge, record-high Q ⋅ f products for their fundamental mode (where Q is the quality factor and f is the frequency). The proposed approach - which can also be used to improve phononic crystals and coupled-mode resonators - opens up a new paradigm for designing ultra-coherent micro- and nanomechanical resonators, enabling e.g. novel experiments in fundamental physics and extreme sensing.