As can be confirmed via Memory Alpha, the service years of the ships named "USS Enterprise" in the original timeline beginning at 2245 are:
NCC-1701 (Captains April, Pike, Kirk, Decker, Kirk, Spock), years 2245-2285 (destroyed under command of Admiral Kirk, acting captain)
NCC-1701-A (Captain Kirk), years 2286-2293
NCC-1701-B (Initial commission under Captain Harriman, later captain(s) unknown), years 2293-?
NCC-1701-C (Initial captain(s) unknown, final commission under Captain Garrett), ?-2344 (lost to Romulan Star Empire under command of Lt. Commander Castillo, acting captain)
NCC-1701-D (Captains Picard, Riker, Picard, Jellico, Picard), 2363-2371
NCC-1701-E (Captain Picard, later captain(s) unknown*), 2372-?
We all know that the Enterprise-A was a gift to Kirk for saving Earth — hence, this Enterprise was quickly recommissioned for him (it had been the USS Yorktown until then).
However, the Enterprise-B was rapidly commissioned in 2293, the same year the A was decommissioned.
I cannot find canonical data regarding the decommissioning of the B and the commissioning of the C. However, why was there a two-decade gap between the loss of the Enterprise C at Narendra III and the commissioning of the Enterprise D, given the prestige and general continuity of the Enterprise in Starfleet?
*Captained in and around 2387 by Captain Data / B-4, if you believe Countdown....