The Okinawa was Benjamin Sisko's assignment prior to his posting on the USS Saratoga. On the Okinawa, Sisko was promoted to lieutenant commander and received the position of executive officer under the command of Captain Leyton. The Okinawa saw action in the Tzenkethi War.
On one occasion, the Okinawa encountered three Tzenkethi raiders, which then fled into a nearby asteroid belt. Commander Sisko told Captain Leyton it was risky to pursue them, but was overruled by his commanding officer. In 2372, Sisko admitted that going after the Tzenkethi was the right thing to do. (DS9: "Homefront", "Paradise Lost")