We calculate for the first time the complex potential between a heavy quark and antiquark at finite temperature across the deconfinement transition in lattice QCD. The real and imaginary part of the potential at each separation distance r is obtained from the spectral function of the thermal Wilson loop. We confirm the existence of an imaginary part above the critical temperature T(C), which grows as a function of r and underscores the importance of collisions with the gluonic environment for the melting of heavy quarkonia in the quark-gluon plasma.