Among Shevardnadze's early efforts to consolidate power and bring stability to Georgia, his greatest crisis was caused by military losses in Abkhazia in 1993–94. After Abkhazia's Supreme Soviet declared independence in July 1992, Georgia sent in troops to quell the secession. Shevardnadze had pursued peace talks with mediation by Russia's Foreign Ministry. In September 1993, the breaking of a ceasefire and heavy fighting caused Shevardnadze to fly to Abkhazia to take personal command, but the Abkhazians, with the aid of Chechens and other mercenaries (and connivance of some Russian military elements in Abkhazia), drove out all Georgian forces. Georgian and Abkhazian officials signed a Russian-brokered ceasefire in May 1994. As part of this agreement, Russian troops, formally acting as Commonwealth of Independent States (CIS) "peacekeepers," were deployed in a security zone along the Inguri River, which divides Abkhazia from Georgia. Shevardnadze stated in June 1997 that he had been forced to permit the CIS "peacekeepers" into Abkhazia because the United Nations (UN) had balked at sending a sizeable force.
Another major crisis took place when Gamsakhurdia and his supporters launched an insurrection in the Mingrelian area of western Georgia and marched on Tbilisi. Shevardnadze appealed to Russia for assistance, and Russia's tank forces were instrumental in quelling the insurrection. As part of the price for Russia's military aid in defeating Gamsakhurdia, Georgia entered the CIS in 1993, and Shevardnadze signed the CIS Collective Security Treaty, a Russian-Georgian Friendship Treaty, and border troop accords. (Russia's legislature has refused to ratify the latter.) Georgia's entrance into the CIS was regarded as anathema by many Georgians, though Shevardnadze stressed the "realism" of accommodating Russia at that time. In March 1995, the two sides signed a treaty granting Russia rights to four military bases through the year 2020. The Georgian legislature refused to ratify this basing accord. Although Shevardnadze initially viewed the basing agreement as a means to entice Russia to support Georgia's interests in settling the Abkhaz conflict, his government in the late 1990s called for removing the bases. Shevardnadze reportedly received strong U.S. and Western support in pressuring Russia to close two of the bases by mid-2001, and to discuss closing the other two as part of the adaptation of the Conventional Armed Forces in Europe Treaty in November 1999. In January 1999, Georgia assumed full control over guarding its sea borders, and on 15 October 1999, the last Russian border troops left, except for some liaison officers.
As guided by Shevardnadze, a new constitution was approved by the legislature in August 1995. It reestablished a strong presidency, though affirming a balance of executive and legislative powers more equitable than those in most other new constitutions approved by former Soviet republics. Under this constitution, voting for a new legislature took place simultaneously with the race for the recreated presidency on 5 November 1995. In the legislative race, only three of the 54 parties running received at least 5% of the party list vote required to win seats, though other parties won representation through constituency races. Shevardnadze's Citizens' Union Party won the largest bloc of seats, giving him major influence, though the legislature has at times opposed his policies. The election was judged "consistent with democratic norms" by international observers. Legislative elections were held most recently on 31 October 1999. Voting was by party lists (150 seats) and single-member constituencies (73 seats; 12 sitting members representing separatist Abkhaz districts were allowed to retain their seats). At the time of its convocation on 20 November 1999, the Citizens' Union Party held the largest bloc of seats, permitting it to claim the speakership and two of four deputy speakerships. Two other deputy speakers representing Abkhazia (the exiled government) and Ajaria marked a federal element.
In his presidential election manifesto, Shevardnadze stressed economic and social reforms. He called for eliminating poverty, creating a balanced budget, fighting corruption, eliminating wage and pension arrears, and reducing unemployment. He envisaged a five-year plan that would result in ample employment and a "normal" economy. Unfortunately, reforms within Georgia have been slow and corruption in civil and government organizations still runs rampant. In 2001, it was estimated that 60% of Georgians lived below the nation's poverty line. In some cases, those who have jobs have been paying bribes in order to keep them. Though Shevardnadze is viewed as a hero of democracy in the West, Georgian citizens and political critics have little praise for or confidence in his ability to keep his promises for the country.
In November 2001, a controversial raid by state security agents on an independent television station, allegedly for a tax investigation, triggered a demonstration of an estimated 5,000 to 10,000 citizens in the streets of Tbilisi. Protesters echoed the outrage felt by a majority of the nation's citizens and demanded reform in the government. In a surprising response, Parliament speaker Zurab Zhvania, next in succession, put forth his resignation and urged President Shevardnadze to take action. Shevardnadze responded by firing his entire cabinet and promising to restructure the government by creating an office of prime minister to lead a new executive cabinet. The new office would essentially take over many of the duties and power now assigned to the president.