This article analyzes Macedonian foreign policy during the process of joining the North Atlantic Treaty Organization (NATO). We use a modified version of Robert Putnam’s multi-level game concept to show the role of domestic actors in determining Macedonian foreign policy. Based on an analysis of the interactions between the main domestic actors, we identify the reasons for the rapid resolution, after a long pause, of the question of Macedonia’s name and membership in NATO. We use a case-study approach and analyze the available data on the ratio of actors within the existing institutions, key events in the political struggle, and programmes through which the parties formulated foreign policy options. Further, we note the reasons for Greece’s concessions using the concept of multi-level games. We identify a number of important conditions for the formulation of Greece’s position: it is important which party controls the cabinet, whether ruling party coalition partners are ready to support the actions of the cabinet, and whether the actions of the cabinet meet the ideological expectations of other parties. We conclude that three simultaneous conditions made it possible for Macedonia to presently be on the verge of accession to NATO. First, Macedonia’s cabinet was formed by a party ready to accept Greece’s conditions. Second, the party opposed to the country’s renaming occupied less than one third of the seats, making a constitutional majority in the assembly possible. Third, because Macedonian bloc alliances are weak, allies of the anti-renaming party were willing to go against the party forming the bloc.