Madain Saleh (مدائن صالح , also Medain Saleh) is a large archaeological site in Saudi Arabia.
A Nabataean city hewed out of rock in the same style as Jordan's far more famous Petra, Madain Saleh is on UNESCO's tentative list for World Heritage inclusion and would be a top tourist draw in any other country than Saudi Arabia. As it is, though, few foreigners get visa to visit and many Muslims refuse to enter the area due to a section in the Qur'an (Al-Hijr 15:80) often interpreted as a curse against it. For anyone however with a visa it's a must to visit and certainly one of the best sights in the country.
A 100 Riyal permit is necessary for visiting Madain Saleh. Tour operators or hotels will usually arrange these on your behalf (apply at least one week in advance), or do it yourself at the National Museum in Riyadh.
The nearest airports are Prince Abdul Majeed bin Abdul Aziz Domestic Airport in Al-Ula (50 km) and Medina (300 km, and yes, the airport is open to non-Muslims). Until 2004, visitors usually traveled via Hail (400 km), but a new road from Al Wajh now makes that route considerably faster.
The main attraction are of course the rock-carved tombs. You should take most of a whole day to drive around the various rocks. Unfortunately the guides seem to be very light on historic knowledge, and some may make up things as they go along. Reading up on the Nabatean culture before you visit would make the stay more enjoyable, the graves do after all look pretty similar and you may get 'templed out' after seeing two dozen of them without background knowledge. There are no facilities inside the area, take food and plenty of water with you in the car. The area is also nice for hiking among the big rocks, however make sure your police escort allows you to do so. They may not follow you all the time but start a search when they notice you've gone "missing".
A restored Hijaz Railway station can be found on the northern side of the city. Facilities all set up and ready for tourists (as of 2000 anyway), but LOCKED tight as a drum! Travel around inside as much as possible, there are many little interesting things to see. Use of steel sleepers stolen from the railway for all sorts of agricultural uses, and so on.
There is also the old town of Al-Ula just outside the city. The tight quarters of small mud buildings are mostly deteriorated, however as of 2011 the Ministry for Antiques is renovating parts for tourists, an alley was already mostly brushed up at the time of writing. Next to the town is a rock with something like an little fort on top that can be climbed for a nice overview. The old town will usually be part of the tour if you hire a guide for Madain Saleh.
Another destination is the mountain next to Al-Ula from where you can enjoy a panoramic view over the valley if the air is not too dusty. Often your guide will suggest this destination as well.
Lastly, where there are large rocks there is bound to be an "Elephant Rock", and Al-Ula also has its own. Ask you guide for details, it's not far from the city.
During your visit to the Madain Saleh area, you can eat good food in your hotel, (ARAC Al-Ula Hotel 4+ stars), it offers good and clean food, also if you want to try the local food you can visit to nice and clean restaurants in the city of Al-Ula. Your tour guide should guide you to the best places to eat.
Staying overnight at Madain Saleh is not allowed, so most visitors use a hotel in Al-Ula.
You can, if so equipped, camp quite close to the gates of Madain Saleh quite readily. There are organised tours which set up outdoor camps in a very luxurious fashion near the entrance.
Al-Ula/Madain Saleh is as safe as the rest of Saudi Arabia. However, three French nationals were killed in the area in 2007, presumably by terrorists. If you register for visiting the historic sites, a police escort will likely be assigned to your group and follow you around the area. They may also insist on escorting you on your way back on the highway all the way to Medina.