Okay, time for my superior knowledge of Star Trek to clear things up.
The Federation doesn't encounter the Klingons till later. Vulcan has been ****ing around in space for centuries, so they undoubtedly came across a ****load of races the Federation later made first contact with. This isn't a case of explaining away an inconsistency, as the original series(') should've taken this into account.
The Enterprise is the first Warp 5 capable ship. There are hundreds of warp-capable ships coming too and fro from Earth, but the Enterprise is the fastest until the NX-02 comes out of the docks.
Starfleet preceeded the Federation. Starfleet (United Earth Star Fleet) is merged, in 2151, with the United Earth Space Probe to Agency to form the United Earth Stellar Navy.
The Federation is formed 10 years later in 2161, and the United Federation of Planets Starfleet becomes its main military force.
So basically, Starfleet got sucked into the UESN for the 5 years preceding the Romulan War, stayed there throughout the war and was reinstated as an independant naval organization with the founding of the Federation.