We present a state-of-the-art determination of the complex valued static quark-antiquark potential at phenomenologically relevant temperatures around the deconfinement phase transition. Its values are obtained from nonperturbative lattice QCD simulations using spectral functions extracted via a novel Bayesian inference prescription. We find that the real part, both in a gluonic medium, as well as in realistic QCD with light u, d, and s quarks, lies close to the color singlet free energies in Coulomb gauge and shows Debye screening above the (pseudo) critical temperature T-c. The imaginary part is estimated in the gluonic medium, where we find that it is of the same order of magnitude as in hard-thermal loop resummed perturbation theory in the deconfined phase.