At the peak of smuggling of goods in 1990s (especially Supermatch cigarettes) from Kenya into Uganda, a young, brilliant, level-headed lawyer in military fatigues rose to the scene as head of Special Revenue Police Service (SRPS).
He was Col Kale Kayihura a.k.a KK.
Kale - as he was fondly referred to - was by every inch a trusted cadre of President Museveni.
It is perhaps on this account that he was deployed to oversee SRPS, composed mainly of born-again youth picked from various churches around Kampala with diverse qualifications, to neutralise smugglers who had beaten the tax system for years.
These - just like him - were deemed incorruptible. Kayihura did deal a heavy blow to smuggling.
So his coming at the helm of Uganda Police Force (UPF) in October 2005 was clear. A Major General by that time, Kayihura was coming to purge the UPF, which had proved a problem to the "fountain of honour". Worst of all, they always voted "badly".
However, his appointment would be a blessing as it would bring what police lacked - resources. Since the President never trusted those at its helm before him, Kayihura's ascension brought the money from a paltry Shs58 billion to Shs600b a year.
Taking over from Gen Katumba Wamala, Kayihura inherited a force that was in the middle of fighting armed robberies of cash, cars and murders.
Running away from the Operation Wembley whose name had become tainted under Brig Elly Kayanja, Kayihura created the Violent Crimes Crack Unit (VCCU) headed by David Magara.
The VCCU's operations were a success as guns were recovered, some robbers were killed and others fled abroad.
Kayihura ensured police reached the remotest parts of the country to an extent that in some areas, officers were the first sign of government presence.
Under his leadership, he built a police headquarters and saved the Force huge sums of money in rent every month.
Kayihura committed and developed police training at Kabalye where a citizen had donated land to his predecessor Gen Katumba Wamala.
He also built a sizeable number of police stations with some accommodation around the country.
On many occasions, Kayihura apologised for his officers' misdeeds, especially where it involved death. Often times, he paid compensation to affected families.
Kayihura was a policeman in uniform but lacking in policing matters. He was good at developing police theories which when transformed to the ground yielded no results.
A good example is the community policing model which is opposite of what it was meant to be.
He was a man loved by the public for his display of what police can do but loathed by the men in uniform for his poor administration.
He run roughshod over the Opposition and brought him many political enemies but accolades from his boss President Museveni. He would soon be elevated to the rank of General.
His appointment saw the immediate exit of senior officers such as Eric Turyatunga, Gabriel Opio Odoket, etc whose stewardship would have come in handy.
His methods of work not only saw officers with experience leave but even young but promising officers quit, seeing no direction.
With "negative energy" out of the way as Gen Kayihura used to refer to his deputy Julius Odwe, he was now in full control of the Force.
He introduced a notion that ranks were not attached to office, so anybody could be deployed anywhere. He elevated desks into directorates. Thus from four, it soon had 24.
In the training section, his first victim was Fred Nabongo who was director of training.
Nabongo had opposed his idea of taking police officers to Kyankwanzi political school because he thought it would indoctrinate policemen into cadres of the NRM.
He handed the office to the inexperienced and young Andrew Felix Kaweesi (RIP).
With declining professional image, the recruitment started taking on officers of who-is-who in the NRM. The NRM mobilisers at village level also got a nod for jobs in UPF.
This was the first sign of the birth of indiscipline in the Force. On deployment, the officers were no longer answerable to their line managers but would call Kaweesi or Kayihura directly; a thing that had been unheard of in the force's history for a recruit to call an IGP. It became so rampant leaving senior officers at the mercy of their juniors.
With dejected senior officers, Kayihura saw an opportunity to fast-track the promotion of junior officers to senior positions with some jumping a rank or two. Some officers cashed in on the promotions but were not followed with training.
Kayihura's assumption that the junior officers would fit into senior positions yielded no results as they fell flat in the fight against crime.
They were not glued in actual policing as they needed some years with the mentorship of their senior colleagues. Poor training and work frustrations saw officers mete out brutality on the masses as they quelled civil demonstrations.
Kayihura resorted to a few individuals he felt would do the job, he gambled by transferring a few willing senior officers who seemed to support him to critical areas.
It was not strange to transfer director of Counter Terrorism to head another directorate where he totally lacked expertise like Kampala Metropolitan Police (KMP).
However, his worst nightmare was Operations directorate from where he had removed Francis Rwego to head the Interpol Sub-regional bureau in Nairobi, Kenya.
Since then, the directorate has changed hands over six times, including Andrew Felix Kaweesi. All this earned Kayihura a constant bashing from his deputy Julius Odwe who never tired authoring dossiers about his boss' methods of work and how he was running down the force to the Minister of Internal Affairs.
Kayihura often appointed and deployed officers only to turn around and accuse them of being incompetent.
Senior officers resorted to playing it safe only waiting to be assigned by the boss lest they do anything that may not go down well with him thus the birth of a common police term 'match timing' or staying on until retirement.
Desperate to prove the police were in control of crime, Kayihura recruited more Special Police Constable (SPCs). The result was disastrous as trigger happy SPCs were killing people all over.
He then ordered the removal of the big inscription "SPC" at the back of their blue uniforms and regularised them as police officers.
When David Magara - who had managed to shield off his boss' poor policing - retired from VCCU, Kayihura created the Special Investigation Unit (SIU) to handle high profile corruption cases.
It is here that big corruption cases were brought to the fore. However, some of these cases never saw the light of day after the lead investigator then Grace Akullo sought to prosecute some 'untouchables' and she was denied facilitation.
With Magara no longer within reach to counter violent crime, Kayihura took on Nixon Agasirwe, an SPC with questionable background, into VCCU to help out.
In total disregard of Agasirwe's past, Kayihura elevated him from an SPC to the rank of Inspector of Police. This created so much anxiety in the force but the grumbling soon died down.
One of Kayihura's early mistakes in the Force was the disbandment of Special Branch.
Police no longer had its own intelligence; it relied on other sister organisations such as CMI and ISO. There were often disagreements as to who had arrested a suspect or suspects as each sought to outwit another before the President.
Amid this, the public suffered the heaviest blow as police services were given out depending on who was seeking them or who paid for them.
Corruption was no longer a thing to hide as young officers sought to enrich themselves. By creating the Police Professional Standards Unit (PSU), Kayihura shot himself in the foot; the new breed of police officers he recruited were major suspects.
With all this he resorted to "fire-brigading", visiting every scene of crime where he would hold press conferences which often tampered with collection of evidence.
In his fight against crime, Kayihura played to the gallery, managed police crime reports to reflect a rosy picture of the crime situation yet in actual sense it was deteriorating.
He stopped releasing them altogether with no report in the last three years.
Over the years, police investigations became so poor that it was not strange to free a known criminal but lock up an innocent man.
Cases of coercion through torture to admit criminal liability became rampant, a true reflection of a failed investigative machinery.
Members of the Boda Boda 2010 Association and "crime preventers" were his main intelligence arm.
It was not strange for Kayihura to meet a crime preventer and not a police officer. Kayihura consumed and acted on raw intelligence, leaving a string of mistakes in his wake.
As Kayihura run up and down to prove to his boss that he was in charge, it wore both him and his officers down.
The bulk of the police budget went to none core police functions like community policing with no real results to show.
At the time of his exit, Kayihura leaves behind a polarised force, unable to pay its bills, a deeply stressed, highly undisciplined and infiltrated force.
As Okoth-Ochola takes up the ruins, he has an uphill task to deal with internal force discipline, pay debts, comfort officers who have endured 12 years of distress and tongue lashing from their former boss.
To achieve this Okoth-Ochola might need to request all those recruited in the last 12 years to re-apply to join the force and put others under investigation.
He might need to co-opt retired police officers to re-direct investigations to address the rampant murders, robberies and kidnappings, many of which are linked to operatives in security agencies, including the police.
He will need to take bold steps to protect police land and deal with the "11 million" crime preventers who dot police stations countrywide.