If you're a gay traveler looking for a new and different destination, pack your bags and head to Mormon country.

That's right: Salt Lake City. "This beating heart of the Church of Jesus Christ of Latter-day Saints is rife with a vibrant young gay community, lots of bars and a mayor who pushes for gay rights," writes Ed Salvato, travel editor for PlanetOut.com.

MOST POPULAR STORIES New arrests likely in Fla. adoptive couple slaying Toddler found wandering street alone Reed aims to rejuvenate Christian conservatives Motorist dies in drive over edge of Grand Canyon Three arrested for attempted robbery near Tech
EMAIL THIS PRINT THIS MOST POPULAR

The city makes his top five list of surprising gay-friendly getaways: places with plenty of lesbian and gay bars and clubs, a variety of gay-flavored restaurants and policies that encourage tolerance of diversity. "Yet these cities rarely appear on gay travelers' lists when 'staying gay' is the priority," Salvato said.

Stay ahead of the crowds and check out Salvato's picks:

Osaka, Japan: "Hedonistic Osaka, Japan's second city, glitters with futuristic architecture, excellent shopping, world-class restaurants, vibrant nightlife and stylish residents. Gay quarter Doyama-cho offers more than 20 bars for men, several women's options and an array of club nights."

Valencia, Spain: "Spain's third-largest city basks contentedly on the sun-saturated coast south of Barcelona. Surrounded by dramatic mountains and glorious orange groves, the city boasts its own fantastic scenery — impressive architecture, a character-steeped old town and lively lesbian and gay bars. Catalonia Excelsior (Barcelonina 5; 34-96-351-4612) is a hotel in the central square that has a vast Jacuzzi."

Phoenix: "With 12 percent of the population estimated to be gay, things in the Valley of the Sun are certainly heating up. Phoenix's ever-improving dining and nightlife scene warms its visitors. Pookie's Cafe (4540 N. Seventh St.; 602-277-2121) is a popular restaurant/nightspot frequented by men and women who come for the inexpensive prices, large portions, friendly staff and fun atmosphere."

Salt Lake City: "The Mormon metropolis has an enticing gay side, great gay-favored restaurants and even a "gayborhood" in the leafy area around Ninth East and Ninth South. Although a freak tornado, dubbed "the Whirlwind of the Lord," destroyed the city's oldest gay bar in 1999 (much to some [residents'] satisfaction), SLC still offers distinctive nightlife, including 10 taverns and private clubs. The Trapp (102 S. 600 West; 801-531-8727) is a haven for cowboys and locals. Women should wander to MoDiggity's (3424 S. State St.; 801-832-9000), the busiest lesbian club."

Madison, Wis.: "Gays and lesbians find a warm welcome in Madison, a surprising Midwest oasis of diversity, openness and cultural activity, as well as home to the only out lesbian member of the U.S. Congress, Tammy Baldwin. Influenced by the liberal-leaning University of Wisconsin, Madison was at the forefront of American cities banning discrimination based on sexual orientation. The gay-popular 11-room Mansion Hill Inn (424 N. Pinckney St.; 608-255-3999; www.mansionhillinn.com; $145-$325) is near the university."