In 2266, Balok encountered the Federation starship USS Enterprise entering the borders of the First Federation. Unsure of how to react to the strange vessel, Balok sent out a cube-shaped warning buoy to scare the Enterprise away. However, when the Enterprise destroyed the buoy, Balok took the Fesarius to intercept them. Wanting to appear more threatening he communicated with Captain Kirk using a fearsome looking dummy. He wanted to test if the human crew were hostile, so tested them, by first threatening to destroy them, and then testing their compassion.
Fortunately, Captain Kirk and his crew were a compassionate people, and Balok invited a small team aboard the Fesarius. Balok was most impressed with the human crew, and gave them a tour of a First Federation base. As part of a cultural exchange, Lieutenant David Bailey was to remain behind with Balok. (TOS episode: "The Corbomite Maneuver", and novel: Preserver).
After exploring the Alpha Quadrant with Bailey for around 20 years, the two decided to continue their explorations into the Delta Quadrant. Their next contact with anyone from the Federation came in 2373, when Captain Kathryn Janeway and the crew of the USS Voyager rescued Bailey from the Mondasians. As a thank you, Balok escorted Captain Janeway on a tour of the Fesarius. (VOY short story: "Ambassador at Large").