He served in various Ugandan militaries from 1965 until 2013, including under the governments of Milton Obote, Idi Amin, Tito Okello, and Yoweri Museveni.

Alongside other remnants of the Ugandan military, he retreated into exile in 1979 and subsequently became part of a rebel group attempting to overthrow the government in Uganda.

In 1985, the new Ugandan government was overthrown by its own military; Rwehururu subsequently returned from exile and joined the Uganda National Liberation Army (UNLA).

If he continued his education to become a priest, he would only be able to make any money after seven years; as a result, he abandoned his studies and enlisted as an officer cadet[3] in the Uganda Army (UA) in 1965.

[3] By 1973, Rwehururu was a Company Sergeant Major, and took part in military exercises at the border of a neighboring state, Tanzania.

[11] Rwehururu was among the small number of military officers of non-West Nile origin who stayed loyal to Amin's government during the Uganda–Tanzania War.

[12] By December 1978, the Tanzania People's Defence Force (TPDF) had repelled the initial Ugandan invasion and was preparing a counter-invasion.

[9] On 22 January, a helicopter carrying Brigadier Taban Lupayi and Lieutenant Colonel Godwin Sule reached Sanje; the officers informed Rwehururu that the reinforcements which had been promised to him were coming from Lukaya, 120 kilometres (75 mi) north of Mutukula.

[17] The TPDF stormed Masaka on the next day,[18][19] and what remained of the Ugandan garrison was routed; Rwehururu later argued that he "lost control" of the situation.

[26] However, journalists Tony Avirgan and Martha Honey –who accompanied Tanzanian troops during the war– stated that the Ugandan Tiger Regiment, not the Suicide Battalion, had fought at Sembabule.

[28] On 11 April, Uganda's capital of Kampala fell to the Tanzanians and their rebel allies; Amin subsequently fled into exile.

[30] When the Uganda Army troops in Masindi heard that the TPDF had also captured Hoima, most of them panicked and fled for Kigumba.

Believing that he had to delay the Tanzanian advance to ensure a more orderly retreat of the UA troops, Rwehururu rallied the Suicide Battalion and set up an ambush on the Masindi-Hoima Road.

[33] Rwehururu was among these forces, but the ex-Uganda Army troops were never able to substantially expand their operations beyond West Nile District.

[3] In 1985, the government of Milton Obote's second presidency was overthrown by its own armed forces, the Uganda National Liberation Army (UNLA).

[2] In 2002,[35] he published an autobiography, titled Cross to the Gun, in which he detailed his experiences during Amin's rule and, according to the Daily Monitor, attempted to "decipher what went wrong with the country's political and military class".

[2] UPDF commander Katumba Wamala praised Rwehururu as "a knowledgeable, humourous [sic] and smart officer".