Dagestan is the Caucasus in miniature, and then some. It is a republic of about 50,000 square kilometers (19,000 square miles) where over 30 ethnic groups are counted and 14 official languages, where the first Muslims on today's Russian territory arrived after the Arab conquest of 643, and where a Sasanian shah once walled the narrow strip between the sea and the mountains so that nomads couldn't ride south. That wall is still standing in Derbent, and it is the reason this place was ever a crossroads.
The country is split in two. On the Caspian coast there is Makhachkala, a loud city of roughly a million people in its agglomeration, and Derbent, which calls itself the oldest city in Russia. Inland, within two or three hours of the coast, the road climbs into canyons, abandoned stone villages and plateaus at 1,500 to 2,000 meters. Five days is enough for one honest pass: the coast, one big canyon, one night up in the mountains. It is not enough for all of it, and a few places had to go to the end of the guide.
Read the practical part before you book anything. Dagestan is a place where the UK Foreign Office and the US State Department both have strong words, and where travel insurance may not cover you, so the first tips on this page say plainly what the governments say and what that means. The plan itself is Makhachkala and the Sarykum dune on day one, Derbent on day two, the Sulak canyon on day three, then a night in Gunib with Karadakh, Gamsutl, Khunzakh and Matlas on days four and five. For the wider picture, including visas and how to pay, see Russia. Start on a Monday: Derbent falls on a Tuesday, well away from Friday's main prayer, the canyon on a quieter Wednesday, and the Khunzakh museum (open Tuesday to Saturday) on Friday.