Nelestra was a planet located somewhere between Federation space and the Aquarius Formation. In the 2270s, the planet was found to be inhabited by a humanoid species by the crew of the USS Enterprise.

Captain James T. Kirk and Lieutenant Pavel Chekov formed part of a landing party that beamed down to the planet and met with the planet's leaders. As a gift to Kirk and Chekov, the leaders presented them with half-a-dozen nubile women, however, when Kirk protested that the women would not influence his mission to establish diplomatic relations, the leaders presented them with more women.

In 2293, Chekov recalled this tale to the former command staff of the Enterprise, as part of an informal gathering at Kirk's apartment following his memorial service. (TOS novel: The Fire and the Rose)

planets visited by the USS Enterprise (NCC-1701) (2273-2285)
Admiral Kirk's command (from 2273) EarthNelestraZaran IILevaeri VStarbase 16 planetAndrea IVAgena IVMycenaStarbase 8 planetBarak VIIAndronicusStarbase 28 planetPhaetonHephaestusZeta Reticuli IIStarbase 9 planetLieberman's WorldMiaplacidus VValerianGoran IVZenna IVplanet of telekinetic herdsYkoParides IVKhepriPollox IVUpsilon Xi IIIBelle TerreLycos V
Spock's command (until 2285) EarthThieurrullStarbase 12Regula Admiral Kirk's command (2285) EarthGenesis PlanetOrganiaBeta Epsilon VIBabelVulcanRomulan planetoid