The Tholian Assembly was an interstellar nation-state of the Tholian species. In the Alpha Quadrant, the Assembly bordered both the Federation and the Klingon Empire. (TNG: "Conspiracy", "Reunion") The Assembly was wont to unilaterally declare regions of space their "Territorial Annexes".
While there had been sporadic contacts between the United Federation of Planets and the Assembly during the first century of the former's existence, in 2268, USS Enterprise had a hostile encounter with at least two Tholian ships as it attempted to salvage USS Defiant, which had fallen into an interphasic rift. (TOS: "The Tholian Web")
Following this encounter, the Federation constructed an unknown number of Salem-class space stations at the border of Assembly space.
There had been no contacts between the Assembly and the Federation for nearly 27 years, as of late 2294, when newly-minted Ambassador-at-Large Spock was tasked to approach the Tholians. Unbeknownst to many in the Federation, the Tholians and the Vulcans had had diplomatic relations for over three hundred years. (Orion Press: Chekov's Enterprise)
In 2381, following the Borg attack on the Alpha Quadrant -- which resulted in the destruction of many worlds and the deaths of 90 billion beings -- the Assembly joined with several other spacefaring governments to form the Typhon Pact. (TNG novel: A Singular Destiny)