We report on long-term X-ray timing of two anomalous X-ray pulsars, 1RXS J170849.0-400910 and 1E 2259+586, using the Rossi X-Ray Timing Explorer. In monthly observations made over 1.4 and 2.6 yr for the two pulsars, respectively, we have obtained phase-coherent timing solutions which imply that these objects have been rotating with great stability throughout the course of our observations. For 1RXS J170849.0-400910, we find a rotation frequency of 0.0909169331(5) Hz and frequency derivative -15.687&parl0;4&parr0;x10-14 Hz s-1 for epoch MJD 51215.931. For 1E 2259+586, we find a rotation frequency of 0.1432880613(2) Hz and frequency derivative -1.0026&parl0;7&parr0;x10-14 Hz s-1 for epoch MJD 51195.583. The rms phase residuals from these simple models are only approximately 0.01 cycles for both sources. We show that the frequency derivative for 1E 2259+586 is inconsistent with that inferred from incoherent frequency observations made over the last 20 yr. Our observations are consistent with the magnetar hypothesis and make binary accretion scenarios appear unlikely.