The article studies the establishment of Russian diplomatic missions in the Maghreb (Algeria, Morocco and Tunisia) in late 18th - 19th century. Studying the outset of the Russian-Arab relations is a significant task for both science and diplomacy. Although there are several works dating from the Soviet era, the issue remains little-studied. The article draws on the documents from the Archive of Foreign Policy of the Russian Empire, some already published, others introduced into scientific use for the first time. Analysis of archival sources allows to consider the problem of first contacts of the Russian Empire and the Maghreb states in its entirety, to identify Russian interests in each of three countries, to define important internal and external factors that prompted the countries to establish relations. The author has revealed that at the first stage of the Russian-Maghreb relations its economic component had a priority: foreign representatives in the Maghreb were enlisted as non-staff Russian consuls in order to protect the interests of seamen-merchants trading in the Mediterranean under the Russian flag. At the second stage priority was given to the political component in the Russian-Maghreb relations. The great power directly involved in the settlement of the Eastern Question, the Russian Empire had to consider Algerian, Tunisian and Moroccan factors in setting its European agenda. The Russian government saw the Barbary states of Algeria and Tunisia as formally belonging to the Ottoman Empire. Russian political interest in these countries strengthened as the European powers, primarily, France and Great Britain, were fighting to establish their influence, and Turkey strived to preserve its sovereignty. Although it remained independent throughout the 19th century, Morocco also was an object of the European powers' rivalry. Russian diplomatic missions in Algeria, Tunisia and Morocco were established with an eye toward keeping track of all twists and turns of the European powers fighting over the North African colonies and in order use this factor in setting its own agenda.