The Traoré regime was under mounting international and domestic pressure for democratisation when the insurgency emerged. President Traoré realised that a swift military victory was impossible, making the possibility of a negotiated settlement more attractive. The Algerian government was concerned with internal security and feared an uncontrollable situation on its southern border that might draw in the disaffected Tuareg population in Algeria. It became very active in supporting peace initiatives to address the conflict in Mali. Within Mali, President Traoré began to pursue strategies to influence the northerners. First he turned to a traditional chief who was comparatively close to his government, Intallah Ag Attaher, for mediation. However, the northern 'youth' viewed the traditional leadership as part of the repressive regime and ignored Attaher. In 1994, they kidnapped him and it became evident that the revolt was not only against the military regime but also against the traditional domination of the Tuareg aristocracy.
The army continued to suffer a series of humiliating defeats and the insurgents recognised that they could negotiate from a position of military advantage. Traoré devoted more time in late 1990 to the Tuareg insurgency than to containing the pro-democracy movement that was gathering momentum in the south. Aware that he needed to stabilise the situation quickly and return troops to the capital, he entered into direct negotiations with the MPA (and later the FIAA) with Algeria's assistance. On 6 January 1991, they signed a peace agreement in Tamanrasset, Algeria. The agreement satisfied the core demands of the movements, including a very high percentage of development funds allocated to the north; integration of nomads into the army, other 'uniformed services' and in all levels of the administration; and greater regional autonomy for managing local affairs according to cultural customs.
But Moussa Traoré had gone too far and did not dare to publish the exact terms of the Tamanrasset Agreement. The opposition was furious at the perceived capitulation of the army and the rumour that the concept of 'autonomy' had been agreed. Although many of the new political parties, students, trade unions and other civil society groups had supported the northern rebellion initially because it threatened the authoritarian regime, many thought Traoré had jeopardised the country's integrity with the agreement. Furthermore, Songhoy communities had not been represented at the Tamanrasset negotiations and many worried that the agreement would install Tuareg dominance in the north, thus fuelling suspicion and tensions within the region.
In March 1991, amidst frequent demonstrations that were violently suppressed, Gen. Adamou Toumani Touré overthrew the regime in a military coup d'etat. He formed a transitional government to guide the country on its way to democracy. Yet the new regime did not consider Tamanrasset Agreement legitimate and made few moves towards implementing it. Under pressure from civil society, in August 1991, the new government hosted a National Conference in Bamako to discuss the future and draft a new constitution.
Although northerners participated in the National Conference, it was not intended as a forum to address the conflict and the insurgency was not on the agenda. Yet on the second day, the 192 northern delegates – men and a few women with positions of status in their communities – met to discuss the situation. They decided to form a commission to follow up on the issues addressed in the Tamanrasset Agreement, where the grassroots had not been represented. The general complaint was of insufficient information and a perception that neither the government nor the movements encouraged popular involvement. Many Songhoy were also negative, believing that the Tamanrasset Agreement failed to pay serious attention to their particular needs. At this stage, however, it was difficult for local civil society to act. Continued violence was exacerbated by the transitional government's inability to control army troops stationed in the north, who wanted to show that they could command the situation. As the army's atrocities against civilians mounted, two new and more aggressive movements emerged: the Popular Front for the Liberation of Azaouad (FPLA) and the Revolutionary Army for the Liberation of Azaouad (ARLA).