Dagestan is a part of the Russian Federation; therefore you will only need a Russian tourist visa to visit the republic. You can get a visa via tourist agencies, who will also get you the necessary insurance.
What may turn out to be more difficult is the so called registration (регистрация) which you should get within three days upon crossing the Russian border. The registration can be acquired in one of the following ways:
•You can ask your tourist agency whether they have a branch office in Moscow that could get you a registration (you have to pay for it).
•You can get a registration in some tourist agency in the Caucasus (unfortunately, it is rather impossible in Dagestan, as tourism is still in its infancy there). You shouldn’t have any problems with getting the registration in Kabardino-Balkaria and Karachay-Cherkess republics; if it’s possible, start your Caucasus journey from the western part of the region, and finish in Dagestan.
•You can ask somebody in Dagestan to register you at their place. In this case you and your host should go to the post office and fill the necessary documents. This is the easiest and cheapest way, however, you cannot use it unless you get closely acquainted with somebody and they will agree to register you at their place.
•Stay one or two nights at the Leningrad hotel in Makhachkala (Rasul Gamzatov street – ул. Расула Гамзатова, former Lenin street) – in this case, the hotel will register you. Of course, you will only have the registration for one or two nights, and not the whole period of your stay, but still it’s better than nothing.
You can always ignore the registration at all and count on policemen’s or border guards’ good mood. However, being decent and law-abiding citizens, we do not recommend this option.
CAUTION: when planning your trip to Dagestan you should bear in mind that it is impossible to get to Azerbaijan from Dagestan and the other way round, as the Russian-Azerbaijani border (same as Russian-Georgian border) is closed for foreigners all along. There are no flights from Makhachkala to Baku or Tbilisi either, and no ferry services to Azerbaijan, Kazakhstan and Turkmenistan.