We calculate the real-time quantum chromodynamic (QCD) static potential in a high temperature medium, beyond the leading order Hard Thermal Loop (HTL) approximation, in the region where bound states transit from narrow resonances to wide ones. We find sizable contributions to both the real and the imaginary part of the potential. The calculation involves loop diagrams calculated in the HTL effective theory and power corrections to the QCD HTL Lagrangian. We compare our results with recent lattice data and check the consistency of different methods used in lattice calculations. We also discuss the usefulness of our results to guide lattice inputs.