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 James T. Kirk using a fearsome looking dummy. He wanted to know if the human crew were hostile, so he 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", TOS novel: Preserver)
After exploring the Alpha Quadrant with Bailey for around twenty 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. In gratitude, Balok escorted Captain Janeway on a tour of the Fesarius. (VOY short story: "Ambassador at Large")