Birhaheka began working for an NGO after completing her university studies. She was hired to work on gender issues as part of their women's department, but encountered the same patriarchal culture within the organization itself.[3] After working on behalf of several other NGOs, and becoming frustrated with the way women were universally sidelined, she and her colleagues decided to create a new NGO to focus specifically on women and women's rights.[3] They founded PAIF, or Promotion et Appui aux Initiatives Feminines (Promotion and Support of Women's Initiatives) in Goma in 1992.[4][5]
The initial mission of PAIF was to improve women's status in public life: to stop women from being relegated to housework and the home, and instead educate them and facilitate their participation in politics, the law, and human rightscauses.[6] They began by working on water supply systems, to allow girls who would otherwise have to fetch water in the mornings to attend school. PAIF also worked to educate both men and women in rural communities about women's rights, using radio stations to promote "the inclusion of women as a development strategy".[3]
PAIF later broadened its mission to include advocacy on behalf of victims of sexual violence. In the aftermath of the Rwandan genocide in 1994, as conflict escalated in the region, Birhaheka became aware of the prevalence of victims of wartime sexual violence among the displaced persons she was working with.[5] She worked to raise awareness of rape as a tactic of war, and to support survivors.[5] PAIF began to provide legal and medical support, especially for those who have been disowned by their families, and to operate a safe house in Goma.[7]
The organization also advocated for greater enforcement and prosecution of rape as a crime.[4] In 2006 PAIF successfully campaigned for reform in the DRC's laws pertaining to rape, including increased penalties for perpetrators.[4][5] Amid ongoing violence in the region, Birhaheka and PAIF continue to raise awareness of issues like sexual exploitation of minors.[8]
Because of her work on behalf of women and survivors of sexual violence, Birhaheka received death threats from within the government and from militia groups. She was detained twice by the Congolese Intelligence Service.[3][9]