The USS Tolstoy (NCC-62095) was a Rigel-class starship in service to Starfleet in the 24th century. (ST reference: Star Trek Encyclopedia)
Captain Christine Parsons took command of the Tolstoy in 2366. (NF short story: "Performance Appraisal")
In early 2367, the Tolstoy engaged the Borg at the Battle of Wolf 359. Unfortunately, the Tolstoy was destroyed in the engagement, along with 38 other vessels. (TNG episode: "The Best of Both Worlds, Part II")
The Tolstoy was destroyed after the USS Kyushu but before the USS Gage in the assault on the Borg cube. (DS9 novelization: Emissary)
- Two different English spellings of this Russian name -- "Tolstoy" and "Tolstoi" -- have been used both in canon and other sources. "Tolstoy" appears to be the one most generally accepted.