High quality factor (Q) nanomechanical resonators have received a lot of attention for sensor applications with unprecedented sensitivity. Despite the large interest, few investigations into the frequency stability of high-Q resonators have been reported. Such resonators are characterized by a linewidth significantly smaller than typically employed measurement bandwidths, which is the opposite regime to what is normally considered for sensors. Here, the frequency stability of high-Q silicon nitride string resonators is investigated both in open-loop and closed-loop configurations. The stability is here characterized using the Allan deviation. For open-loop tracking, it is found that the Allan deviation gets separated into two regimes, one limited by the thermomechanical noise of the resonator and the other by the detection noise of the optical transduction system. The point of transition between the two regimes is the resonator response time, which can be shown to have a linear dependence on Q. Laser power fluctuations from the optical readout are found to present a fundamental limit to the frequency stability. Finally, for closed-loop measurements, the response time is shown to no longer be intrinsically limited but instead given by the bandwidth of the closed-loop tracking system. Computed Allan deviations based on theory are given as well and found to agree well with the measurements. These results are of importance for the understanding of fundamental limitations of high-Q resonators and their application as high performance sensors.