Abstract: Determining the three-dimensional (3D) atomic structure of nanoparticles (NPs) is critical to understand their structure-dependent properties. It is hereby important to perform such analyses under conditions relevant for the envisioned application. Here, we investigate the 3D structure of supported Au NPs at high temperature, which is of importance to understand their behavior during catalytic reactions. To overcome limitations related to conventional high-resolution electron tomography at high temperature, 3D characterization of NPs with atomic resolution has been performed by applying atom-counting using atomic resolution annular darkfield scanning transmission electron microscopy (ADF STEM) images followed by structural relaxation. However, at high temperatures, thermal displacements, which affect the ADF STEM intensities, should be taken into account. Moreover, it is very likely that the structure of a NP investigated at elevated temperature deviates from a ground state configuration, which is difficult to determine using purely computational energy minimization approaches. In this paper, we therefore propose an optimized approach using an iterative local minima search algorithm followed by molecular dynamics (MD) structural relaxation of candidate structures associated with each local minimum. In this manner, it becomes possible to investigate the 3D atomic structure of supported NPs, which may deviate from their ground state configuration.