Fluorescence enhancement by plasmonic nanostructures enables the optical detection of single molecules with weak fluorescence, extending the scope of molecular fluorescence imaging to new materials and systems. In this work, we study single-molecule fluorescence enhancement by individual gold nanorods exploiting a DNA-based transient binding technique. Single molecules are attached to short DNA oligomers that can reversibly hybridize to their complementary docking DNA strands immobilized on the surface of gold nanorods or the glass substrate next to gold nanorods. This method continuously refreshes the single molecule in the near field of the gold nanorod, and enables a study of fluorescence enhancement at a well-defined position, with long dwell time and without limitation by photobleaching. Docking strands attached to the glass substrate are found to be more photo-stable. We find over 3000-fold fluorescence enhancement of single molecules of IRDye800CW, a near-infrared dye with a low quantum yield of 7%. This strong enhancement, consistent with numerical simulations, arises from the combined effect of local field enhancement and the competition between radiative and nonradiative decay rate enhancements.