We study the free energy of a heavy quark-antiquark pair in a thermal medium using the AdS/CFT correspondence. We point out that a commonly used prescription for calculating this quantity leads to a temperature dependence in conflict with general properties of the free energy. The problem originates from a particular way of subtracting divergences. We argue that the commonly used prescription gives rise to the binding energy rather than the free energy. We consider a different subtraction procedure and show that the resulting free energy is well-behaved and in qualitative agreement with results from lattice QCD. The free energy and the binding energy of the quark pair are computed for   <math> <mi>N</mi> <mo>=</mo> <mn>4</mn> </math>  $$ \mathcal{N}=4 $$  supersymmetric Yang-Mills theory and several non-conformal theories. We also calculate the entropy and the internal energy of the pair in these theories. Using the consistent subtraction, we further study the free energy, entropy, and internal energy of a single heavy quark in the thermal medium for various theories. Also here the results are found to be in qualitative agreement with lattice QCD results.