In 2293, the location of the First Federation in the Milky Way Galaxy was labeled in a star chart that was in Captain James T. Kirk's quarters aboard the USS Enterprise-A. (Star Trek VI: The Undiscovered Country, okudagram)
First contact between the Federation and the First Federation occurred in 2266, when the USS Enterprise was conducting a star mapping mission and unknowingly crossed into First Federation space, destroying a marker buoy in the process.
Shortly thereafter, the Enterprise encountered the massive flagship of the First Federation, the Fesarius. Charged with violating their territory, the Enterprise and its crew were threatened with destruction. However, after a series of bluffs and counter-bluffs, it was discovered that the encounter had only been a test, designed by the Fesarius' captain, Balok. A cultural exchange was proposed, with Enterprise crewman Dave Bailey remaining on board the Fesarius. (TOS: "The Corbomite Maneuver")
According to Star Trek: Star Charts (Pg. 36, "United Federation of Planets I"), the First Federation was located in the Alpha Quadrant. The First Federation's capital system was Fesarius. Fesarius was a Class K star with a magnitude of +3, which was ten times the brightness of Sol. A major space lane was located in proximity to the territory of the First Federation. Warning buoys had been installed by 2378 around the First Federation's territory.