This chapter will show that Russia is attempting to regain the lost strategic positions it claimed before the end of the Cold War, and to assert Moscow’s overall ambition to become again a notable foreign power in Africa after abruptly abandoning its stakes there. This task would require not only investments of capital but also of trust in times of increased international competition in the strategic Northeast Africa. During the Cold War, the Soviet Union’s focus on East Africa was centered on obtaining and maintaining access to the ports of the Horn of Africa, when shifting alliances between Ethiopia and Somalia complicated its relations with the United States. At present, Russia is facing a far more challenging regional setting, with Africa’s economic resurgence and growing economic prospects, and the increased interests from a variety of international actors, including China, EU, US, Turkey, India and Brazil. Thus, the previous accent on the military and the political forms of engagement has shifted to the introduction of more flexible economic forms of interaction based on mutual interest.