Stavropol — this capital city is located in a particularly mountainous area of the region and was one of Russia's most important bases during the Russian conquest of the Caucasus; former home to Mikhail Gorbachev and it has a particularly nice urban park
Essentuki — yet another Caucasian health spa resort with mineral waters, hot springs, sulphide mud baths, and a small, pretty wooden church
Kislovodsk — meaning "Sour Waters," home to Alexander Solzhenitsyn
Lysogorskaya Stanitsa — a small Cossack village not far from the health spa cities with a beautiful 19th century wooden church
Pyatigorsk — major Russian health spa destination surrounded by the five peaks of Beshtau made famous by Lermontov's A Hero of Our Time, and the site of Lermontov's death by duel on Mount Mashuk
Stavropol Krai contains a large number of Caucasian health spas/sanatoria, which Russians have visited for over 200 years to treat various ailments (and just to escape the northern climate of Moscow and Saint Petersburg. As such, the region has been home to many of Russia's most prominent figures, including writers such as A.S. Pushkin and Mikhail Lermontov, whose works have embedded the Pyatigorsk region into the national consciousness. A great read for anyone visiting the region is Lermontov's short novel, A Hero of Our Time, which is set in various areas in the south of the Krai.
Stavropol Krai is also notable for its exceptionally diverse climactic and topographic diversity. The environments range from sand deserts, to mud flats, to steppe, to forest, to mountains, to permafrost!
By rail, most visitors will arrive at the regional transit hub of Stavropol. Domestic flights to Stavropol and to Mineralnye Vody (which is closer to Mount Elbrus, the Northern Caucasus, and the health spas) are common around Russia. Visitors flying into the Mineralnye Vody airport should note that it is an exceptionally weird and unpleasant airport, even by Russian standards, with very corrupt officials. They will, however, probably be thrown off by rare Western tourists and avoid extorting bribes.
Because of its proximity to the conflict in Chechnya, the security situation is very poor in Stavropol Krai. While kidnappings are unlikely, there have been fairly regular bombings of public areas and official facilities in the southern cities and in Stavropol over the years. While a visitor is fairly unlikely to be victim to such terroristic attacks, the resulting crackdown has led to strict and unfortunately corrupt policing of the area — a visitor is quite likely to be harrassed for bribes.
Stavropol Krai is a common jumping off point for tourists venturing into the Northern Caucasus. Basically any city in the region can be reached via minibus or taxi from Mineralnye Vody.