The gluon condensate is very sensitive to the QCD deconfinement transition since its value changes drastically with the deconfinement transition. We calculate the gluon condensate dependence of the heavy quark potential in AdS/CFT to study how the property of the heavy quarkonium is affected by a relic of the deconfinement transition. We observe that the heavy quark potential becomes deeper as the value of the gluon condensate decreases. We interpret this as a dropping of the heavy quarkonium mass just above the deconfinement transition, which is similar to the results obtained from QCD sum rule and from a bottom-up AdS/QCD model.