The original Treaty on Conventional Armed Forces in Europe (CFE) was negotiated and concluded during the last years of the Cold War and established comprehensive limits on key categories of conventional military equipment in Europe (from the Atlantic to the Urals) and mandated the destruction of excess weaponry. The treaty proposed equal limits for the two "groups of states-parties", the North Atlantic Treaty Organization (NATO) and the Warsaw Pact. In 1999, the Adapted CFE was signed to take in consideration the changed geopolitical realities and the disbanding of the Warsaw Pact, but NATO refused to ratify it, citing Russian failure to comply to the Istanbul Commitments. In 2007, Russia "suspended" its participation in the treaty, citing the US presence in Eastern Europe and NATO's refusal to ratify the Adapted CFE treaty. On 10 March 2015, citing NATO's alleged de facto breach of the Treaty, Russia formally announced it was "completely" halting its participation as of the next day. On 7 November 2023, Russia withdrew from the treaty, and in response the United States and its NATO allies suspended their participation in the treaty.

In 1972, US president Richard Nixon and Soviet General Secretary Leonid Brezhnev reached a compromise agreement to hold separate political and military negotiations. The Conference on Security and Cooperation in Europe (CSCE) would deal with political issues, and Mutual and Balanced Force Reductions (MBFR) with military issues. The CSCE resulted in 1975 in 35 nations signing the concluding document: the Helsinki Final Act. Negotiations for MBFR were stalled by the USSR in 1979 because of NATO's decision to deploy new intermediate-range nuclear weapons in Europe. In 1986, Soviet General Secretary Mikhail Gorbachev proposed in the context of MBFR negotiations to reduce ground and air forces, and to include conventional and nuclear weapons from the Atlantic to the Urals. This proposal was formalized later that year during a Warsaw Treaty meeting. NATO's North Atlantic Council of foreign ministers issued the Brussels Declaration on Conventional Arms Control, which called for two distinct sets of negotiations: one to build on the Confidence and Security-Building Measures (CSBM) results of the Stockholm Conference and the other to establish conventional stability in Europe through negotiations on conventional arms control from the Atlantic to the Urals (ATTU). In 1987, the Stockholm Document entered into force and for the first time provided a negotiated right to conduct on-site inspections of military forces in the field.

Informal talks between the 16 NATO and the 7 Warsaw Treaty nations began in Vienna on 17 February 1987 on a mandate for conventional negotiations in Europe, which would set out the treaty negotiating guidelines. Several months later, on 27 June, NATO presented a draft mandate during the 23-nation conference in Vienna. The mandate called for elimination of force disparities, capability for surprise attack, and large-scale offensive operations, and the establishment of an effective verification system. Meanwhile, in December the INF Treaty between the United States and the Soviet Union was signed, effectively allowing mutual inspections. During the May–June 1988 Moscow Summit, US President Ronald Reagan and General Secretary Gorbachev emphasized the importance of stability and security in Europe, specifically calling for data exchange, verification of these data, and then reductions. In December 1988, Gorbachev announced in the United Nations a unilateral withdrawal of 50,000 troops from Eastern Europe, and demobilization of 500,000 Soviet troops.

In January 1989, NATO and the Warsaw Treaty members produced the Mandate for the Negotiation on Conventional Armed Forces in Europe. The mandate set out objectives for the CFE Treaty and established negotiating principles, and formal negotiations began on 9 March 1989 in Vienna. When US President George H. W. Bush and France's President François Mitterrand met in May, Bush announced the acceptance of reductions of combat aircraft and helicopters. He also proposed a ceiling of 275,000 personnel stationed in Europe by the US and Soviet Union. Bush's proposal was formally adopted during the 1989 Brussels NATO summit and subsequently presented in Vienna.

In July, the 1989 Polish legislative election held in accord with the Polish Round Table Agreement resulted in the appointment on 24 August 1989 of the first non-communist Prime Minister, considered an effective end of communist rule in Poland, followed in November by the fall of the Berlin Wall in Germany. In the following months revolutions broke out in Hungary, Czechoslovakia, Romania, Bulgaria and Albania. Bush and Gorbachev agreed to speed up arms control and economic negotiations. Bush proposed even steeper reductions, and the Soviet Union negotiated and concluded troop withdrawal agreements with Warsaw Treaty states. The ensuing German reunification would lead to the Treaty on the Final Settlement with Respect to Germany linked to the CFE treaty by specifying that certain military limits imposed on Germany would come into force upon the conclusion of the CFE Treaty.

The text of the treaty was approved by the 22 negotiating states on 15 November 1990 in Vienna.

The Vienna Document on confidence- and security-building measures, also first adopted in 1990, and the CFE Treaty, were seen as parallel peace process components by the Organization for Security and Co-operation in Europe (OSCE).

The Treaty was signed in Paris on November 19, 1990 by 22 countries. These were divided into two groups: