Starfleet's Eleventh Fleet has a brave history behind it. During the Dominion War, it reinforced the Fifth Fleet along the Vulcan border prior to Operation Return, and was thereafter responsible for the protection of Benzar, the homeworld of a key member of the Federation. Unfortunately, therein lay the fleet's destruction, as the Dominion sent a strike force there with superior numbers after sending a decoy in the direction of Alpha Centauri. The Eleventh Fleet was overwhelmed and destroyed before reinforcements in the form of the Fourteenth Fleet could arrive. The Fourteenth Fleet itself lost almost 100 ships in the engagement which followed, and was forced to leave Benzar in the hands of the Dominion, to be re-captured later by the Romulans when they entered the war.
With the end of the war came Starfleet's push to get back to its core goals - exploration and peaceful expansion of the Federation. With so many ships lost, they began to merge the remainders of fleets together, growing the numbers of each individual fleet remaining active, but being forced to either focus their goals in small areas, or spread a fleet out thinly across large areas, where previously up to three fleets patrolled. Eventually, however, lost ships began to be replaced with new ones, and were crewed by higher numbers of entrants to Starfleet Academy than had been seen in most flag officers' lifetimes, and it became possible for Starfleet to once again expand it's organisational structure.
In 2386, with a promotion to Vice Admiral, Roman Sanchez was given the task of reconstituting the Eleventh Fleet, which had remained on the inactive rosters since 2374 and the Battle of Benzar. A former Captain from within the Eleventh Fleet, promoted elsewhere before the ill-fated battle, Sanchez was instructed to gather captains both from the shipyards and from other fleets. Most of the ships Sanchez chose to become a part of the reformed fleet, nicknamed 'Pegasus' after the Admiral's well-known style in battle, were captained by freshly-promoted officers, though a number of ships were also donated to the fleet by other Admirals, and there were a number of transferring commanders joining the fleet too.
With the roster for his fleet coming together, he met with the Commander-in-Chief of Starfleet to discuss the fleet's operational patrol zone. The two Admirals decided to relieve the Fourth Fleet of its patrol zone in the galactic south of Federation territory, allowing the fleet to pull its ships into a closer and more efficient operating area. Though this left the Eleventh Fleet with a significantly larger patrol zone than most other fleets, sharing borders with the Tholians, Klingons, Gorn, and Metrons as well as guarding the forbidden planet of Talos IV, much of the territory, though claimed, was largely unexplored, the farthest reaches of which had only been visited once, by the USS Enterprise on its five-year mission. This left a strong, central 'core' which Admiral Sanchez could focus regular patrols, and plenty of opportunity to explore the farthest reaches of Federation territory and beyond with a central operations centre based at the Cestus III colony, which had grown significantly since being rebuilt after the Gorn-Metron incident involving the Enterprise.