The Tolstoy fought the Borg at the Battle of Wolf 359 in 2367. It was destroyed, along with thirty-eight other starships. When the USS Enterprise-D arrived to the site of the battle, the wreckage of the Tolstoy was seen by Commander Shelby and the bridge crew on the viewscreen. (TNG: "The Best of Both Worlds, Part II")
The Tolstoy was classified as an Rigel-class starship with the registry NCC-62095 in an internal list of starships, dated September 26, 1990. According to this list, the ship was not represented by a model.  This information about the ship later appeared in the Star Trek Encyclopedia (4th ed., vol. 2, p. 403). According to this source, the USS Tolstoy was "named for the Russian author Leo Tolstoy, who wrote War and Peace". StarTrek.com identified the model that was labeled as USS Princeton as the Tolstoy,  and identified the reused Constitution-class saucer model wreck as the USS Princeton. 
Originally, however, the ship that became the Tolstoy was scripted as the "USS Chekhov".  A Springfield-class filming model with the name USS Chekov was in fact seen on screen. A last minute post-production change resulted in Chekov being replaced with Tolstoy in the dialogue, as to avoid a reference to the original series character Pavel Chekov, deemed too "cute" for the moment in TNG: "The Best of Both Worlds, Part II". The Tolstoy's designation as "Rigel-class" was a later invention by Michael Okuda for an internal list of starships. At the time of filming of the episode the class designation was not in use as he remembered, "Rigel: I don't think we ever came up with a ship design specifically tied to that name." 
The depiction of the battle in "Emissary" was originally filmed as a much more elaborate scene than it became. DS9's visual effects supervisor Robert Legato assigned the Tolstoy name to a starship wreck, that was removed from the aired version of the scene. He recalled in Star Trek: Deep Space Nine Companion (p. 18): "I made sure that all of the debris had the correct names on it, the names of the ships that were mentioned in 'The Best of Both Worlds', the starships Tolstoy, Kyushu, Melbourne, and Saratoga were among those described as lost in the battle, so the episodes would tie together."
The Price of Freedom sourcebook described the Tolstoy as a heavy scout with a crew of 65. It had six decks and was 215 meters in length. The ship had a maximum speed of warp factor 9.2. The ship was armed with type VII phaser emitters, and two torpedo launchers with a normal load-out of 75 photon torpedoes.