Sendashonga was a leader of a student movement opposed to the rule of Rwandan president Juvénal Habyarimana and been forced to leave the country in 1975. In 1992 Sendashonga joined the Rwandan Patriotic Front, the rebel group then fighting the Rwandan Civil War against the Habariyamana government. The RPF took power after defeating the Hutu Power-led government that carried out the Rwandan Genocide. Sendashonga was able to use his considerable personal prestige to convince other Hutu moderates to joint the RPF government.
 Minister of the Interior
Following their victory, the RPF created a Government of National Unity in July 1994, and invited Sendashonga, a politically moderate Hutu, to be the Minister of the Interior. For much of his tenure, Sendashonga had written a barrage of memos to Kagame about killings and forced disappearances that were reported to have been carried out by elements of the Rwandan Patriotic Army (RPA). On 19 April 1995, Sendashonga rushed to Kibeho in an attempt to calm the situation after RPA soldiers shot several Hutus in an internally displaced persons (IDP) camp. After returning to Kigali, he briefed Prime Minister Faustin Twagiramungu, President Pasteur Bizimungu and Vice President/Defense Minister Paul Kagame and sought assurances that the RPA would exercise restraint. Following the massacre of a large number of IDPs at Kibeho on the 22nd, the RPA refused Sendashonga entry to the area.
After his attempt to seek redress for the victims of Kibeho was turned down, Sendashonga came to the conclusion that the 'Ugandan Tutsi' who controlled the RPF would not tolerate any dissent and were willing to carry out mass murder to achieve their goals. However, both Sendashonga and Twagiramungu, also a Hutu, thought that the situation might be salvaged as the political split did not precisely mirror ethnic lines; some Francophone Tutsi politicians in the RPF felt excluded by the English-speaking Tutsis who had come from Uganda. Sendashonga decided to take a stand against arbitrary arrests after 15 prisoners had suffocated to death after being detained some days after Kibeho, stating, while cautiously referring to detainees as 'criminals', "Of late many criminals have been arrested following the closure of Kibeho camp, thus making the prisons full beyond their capacity." This infuriated Kagame, who some days before had given a speech proclaiming, "Over 95% of the former Kibeho people have returned to their homes and are in good shape." Tensions in the cabinet worsened after Rose Kabuye, mayor of Kigali, announced the creation of city residency permits that would be given "only to blameless persons" and would be color-coded green for old residents and blue for refugees returning from Zaire, who were suspected of being associated with the old Hutu regime. This announcement panicked the Hutu populace, who rushed to get this vital document, before Sendashonga canceled the entire permit plan through his authority over the Interior Department.
By this point, the RPF Department of Military Intelligence had leaked a memo to the press that stated that Sendashonga, Minister of Finance Marc Ruganera and Vice Prime Minister Col. Alexis Kanyaregwe, all Hutus, were under their watch. As the killings and disappearances continued without any pause, Sendashonga made the dramatic decision to disband the Local Defense Forces (LDF), which had been set up to replace the police after the genocide but were subsequently linked to a large number of arrests, murders and disappearances. However, the LDF was the tool the RPF used to keep track of rural areas, further aggravating Defense Minister Kagame. As a minister, the government could not attack Sendashonga directly, but the RPF began to accuse Sendashonga's brother of various misdeeds. As things reached a breaking point, Twagiramungu called a special council of ministers on security matters that began on August 23. Running for three days, the meeting turned into a conflict between Kagame and Sendashonga, who received the backing of Twagiramungu, Ruganera and, somewhat surprisingly, Aloysia Inyumba, the Tutsi minister of women's affairs. In the final showdown, Twagiramungu confronted Kagame about how, of the 145 bourgmestres appointed by the RPF, 117 were Tutsi, to which Kagame left the room, ending the meeting. Over 95% of the February/March nominees for posts at the local administration levels of paroisse, commune, and préfecture were 'foreign' Tutsi.
Two days later, Prime Minister Twagiramungu resigned, but was outmaneuvered by President Bizimungu, who did not want him to leave the government on his own terms. On 28 August, Bizimungu came before Parliament and asked for a public vote that succeeded in firing Twagiramungu. The next day, Sendashonga, Minister of Transport and Communications Immaculée Kayumba, Minister of Justice Alphonse-Marie Nkubito and Minister of Information Jean-Baptiste Nkuriyingoma were fired. Sendashonga and Twagiramungu were placed under house arrest and their documents examined for any incriminating evidence, but were eventually allowed to leave the country unharmed by the end of the year.
 Exile and assassination attempt
Sendashonga went into exile in Nairobi, Kenya. There he planned to fly to Brussels, Belgium to launch a new opposition movement called the Forces de Résistance pour la Démocratie (FRD) with his old colleague and fellow Hutu moderate Faustin Twagiramungu. In February 1996, Sendashonga received a call from a fellow Rwandan exile offering to give him documents proving that there had been an attempted mutiny within the RPF. When he went to the appointment, he was met by two men who ambushed him, hitting him twice with bullets fired from pistols. His life was not endangered, but his nephew, who was with him, was seriously injured. Sendashonga recognized one of the would-be assassins as his former bodyguard from when he was a minister. The other was Francis Mgabo, a staff member at the local Rwandan embassy, who was subsequently discovered attempting to dispose of the pistol he had used in the attack in the restroom of a local gas station. The government of Kenya asked Rwanda to withdraw Mgabo's diplomatic immunity so he could be arrested and put on trial. Rwanda refused, resulting in a row between the two countries in which Kenya closed the Rwanda embassy and the two countries temporarily broke off diplomatic relations.
After recovering from his wounds, Sendashonga carried out his plan to start the FRD opposition party in Brussels. French historian Gérard Prunier states that the party platform, which included an in-depth critique of the 1994 genocide, was "a very valuable contribution because it was an honest and realistic assessment of the genocide from a mostly Hutu political group." However, Sendashonga's assertion that the enemy was not the Tutsi, but rather the RPF under Kagame, was subject to harsh criticism by other Hutu politicians who accused him of being weak. Conversely, Sendashonga said of the former genocidaire Hutu leadership in refugee camps of Zaire, "Their only political program is to kill Tutsis." At the same time, several of his old Tutsi colleagues in the RPF continued to feed him information about events within Rwanda, apparently in the belief that he would be needed once again once the violence had run its course.
However, Sendashonga realized that only the groups using violence were shaping events, stating to Prunier, "Everybody uses a gun as a way of sitting at the negotiation table one day. If I always refuse to use guns, I'll be marginalized when the time comes." Sendashonga had attracted about 600 soldiers and 40 officers of the old Rwandan Armed Forces, who were willing to fight for him because they saw him as an alternative to the RPF and the Hutu Army for the Liberation of Rwanda, whom they felt were motivated by opposing forms of violent racism. After Tanzania agreed to host Sendashonga's rebel training camps, he used his contacts with Prunier to go to Uganda and talk to Salim Saleh, President Yoweri Museveni's brother, on 3 May 1998. Relations between Uganda and Rwanda had deteriorated and Salim was open to the idea of a new force to counter the RPF. Sendashonga then met Eva Rodgers of the United States Department of State, who was noncommittal but did not outright oppose the formation of the new armed group.
On 16 May 1998, at about 5 pm, Sendashonga was being driven home in his wife's United Nations Environmental Programme car when he was shot and killed, along with his driver Jean-Bosco Nkurubukeye, by two gunmen firing AK-47s. Twagiramungu, still in Brussels, declared, "I'm pointing to the RPF and its government" and was echoed by a number of other exiled political groups, though the RPF government denied any involvement.
Three men, David Kiwanuka, Charles Muhaji and Christopher Lubanga were arrested by the Kenyan police. Kiwanuka was claimed to be Rwandan, despite his typically Muganda name, while Muhaji and Lubanga were identified as Ugandan. The three had been identified, in what Prunier derides as a story "obviously fed by rather untalented Kigali security operatives", by Kenyan taxi driver Ali Abdul Nasser, who claimed that the three men had tried to hire him as a paid killer because Sendashonga had stolen $54 million in a criminal partnership with Kiwanuka's father, who the Nairobi police claimed to have been the Director of Immigration Services in Kigali, and who had subsequently been supposedly killed by Sendasonga so he would not have to share the loot. This story ran into serious problems when the actual Director of Immigration Services, a man named Charles Butera, surfaced to state that he was alive, that he had no son named Kiwanuka, that he knew Sendashonga only as a brief acquaintance, and that nobody had ever stolen $54 million.
Despite the problems with the Kenyan criminal case, the three men remained in jail until 31 May 2001, when they were released from jail by a court. In a December 2000 hearing, Sendashonga's widow, Cyriaque Nikuze, claimed that the Rwandan government was behind the assassination and revealed that he had been scheduled to testify before the International Criminal Tribunal for Rwanda and the French Parliamentary Commission of Inquiry. Sendashonga, who had agreed to testify for the defense in the trial of Obed Ruzindana, would have been the first current or former member of the RPF to testify before the International Criminal Tribunal. Nikuze claims that the Rwandan embassy official Alphonse Mbayire, who was the acting ambassador at the time, organized the assassination. Mbayire was recalled by his government in January 2001, immediately after Nikuze's accusation and shortly before a new hearing was to begin, only to be shot dead by unidentified gunmen in a Kigali bar on 7 February 2001.