Recent geophysical studies have indicated that an earthquake recurrence interval and the size of the preceding event are positively correlated. This observation is the basis for the deterministic time-predictable recurrence model of Shimazaki and Nakata. Using the basic assumptions of the time-predictable recurrence model, we develop a stochastic model of earthquake occurrence that incorporates temporal dependence. This paper discusses the formulation of the model and the effect of including temporal dependence. Hazard estimates for a section of the San Andreas fault near Parkfield, where data has suggested time-predictable behavior, are obtained for illustrative purposes. Comparisons are made with the Poisson model. Results indicate that currently used Poisson models may give lower estimates of the seismic hazard when there has been a seismic gap. Of the various sensitivity analyses performed, it is observed that slip rate has the largest effect on exceedence probabilites computed from the stochastic time-predictable model. Therefore, accurate determinations of slip rates (both seismic and aseismic) can substantially reduce the uncertainty in seismic hazard estimates.