Former Bosnian Serb political leader Radovan Karadzic had thumbed his nose at the West for nearly 13 years - until his arrest on 21 July by Serbian security officers.
Mr Karadzic and Mr Mladic have been indicted for war crimes and genocide
Few details of his arrest have emerged, though Serbian minister Rasim Ljajic said he was intercepted near Belgrade "while changing locations".
Serbia's war crimes prosecutor Vladimir Vukcevic went on to describe how Mr Karadzic had "walked around freely, even appeared in public places", disguised as the alternative medical practitioner Dragan Dabic.
The account astonished many experts, who had assumed Mr Karadzic must have been living in secrecy, surrounded by close allies, not interacting with the public in Serbia's capital.
Radovan Karadzic was drinking coffee at a remote restaurant on the Foca to Gacko road in southern Bosnia
Tales have emerged in recent years of snatched sightings of the fugitive, who would appear relaxed while quaffing a coffee, then would disappear without trace.
The Serbian government regularly claimed Mr Karadzic was not in Serbia, while Nato troops launched several attempts to corner him but were left clutching thin air.
Accused of genocide, Mr Karadzic - along with his military commander Ratko Mladic, who remains at large - had been at the top of the international war crimes tribunal's most wanted list since the transfer of former Yugoslav leader Slobodan Milosevic in 2001.
The BBC's Balkans correspondent, Nick Thorpe, recently wrote about a journalist trying to follow the trail of Mr Karadzic who was warned by Dutch intelligence services: "Don't write about it, if you value your life."
The former Bosnian Serb leader was protected by a mafia ring so powerful that Dutch agents on the case needed protection on their return to the Netherlands, he was told.
A former Bosnian secret agent said two CIA men were found dead after closing in on the war crimes suspect.
THE HUNT FOR RADOVAN KARADZIC
Reportedly seen in Foca, Visegrad and along Bosnia/Montenegro border around time of first reported failed arrest attempt
Celebici - scene of second reported attempt by Nato to capture him in spring 2002
Unsubstantiated claims suggested he might be hiding in monasteries in Trebinje, Ostrog and Frusca Gora
Pale His family home was kept under surveillance
Serb officials said his most recently living in New Belgrade
Met staff from Healthy Living magazine based in Belgrade's Tadeusa Koscuska street
Reported to have given health-related lectures in Sombor, Kikinda, Novi Sad and Smederevo
In April 2004, Nato-led forces carried out a raid on church buildings in Mr Karadzic's former wartime headquarters in the Bosnian Serb stronghold of Pale, which they believed Mr Karadzic was visiting.
He was not there - but a priest and his son were seriously injured in the raid, prompting an avalanche of criticism in the Serbian press.
Nato troops raided the houses of Mr Karadzic's children Sonja and Sasha on 20 February 2007 - again without any result.
Many analysts questioned whether the West really had the political will to risk agents' lives going after Mr Karadzic, despite him being one of the most wanted men in the world.
Carl Bildt, the former UN envoy to Bosnia after the war, told the BBC that members of the alliance had shied away from any action that might have threatened the fragile peace.
"I think there was a sort of collective reluctance by the Nato military commanders - and they weren't [just] American command, but British command as well," he said.
"The reason was they feared that if they moved against him, or against Ratko Mladic, there was going to be significant political disturbances of some sort or another."
Until recently, it was thought the Serbian government shared the reluctance to seize Mr Karadzic - though a change of administration seems to have brought a new attitude.
Mladic's 'military backing'
Mr Ljajic, the Serbian minister, said some details about Mr Karadzic's capture were being withheld, as the authorities were planning to use "operational data" to track the two main war crimes suspects still at large, Gen Ratko Mladic and former Croatian Serb political leader Goran Hadzic.
Gen Mladic, who led Bosnian Serb forces during the Srebrenica massacre, is the prime target.
In 2004, documents leaked by Western diplomats suggested he was still enjoying the protection of the Bosnian Serb military.
He was said to be regularly visiting areas in Bosnia to celebrate birthdays with his wartime colleagues and go hunting in remote forests.
In an unprecedented move, EU peacekeepers in Bosnia opened up a secret Bosnian Serb underground military complex near the town of Han Pijesak.
Journalists were invited to the bunker where, it was claimed, Gen Mladic had been as recently as July 2004. A Nato-led operation at the time failed to find its man.
It was also revealed that Gen Mladic had still been an official member of the Bosnian Serb military as recently as 2002 and was still receiving a military pension.
Heat stepped up
But although Gen Mladic is originally from Bosnia, there have been strong rumours that his real support has come from elements within the military and intelligence services in neighbouring Serbia.
Leading Serb politicians have admitted for some time that democratic control over every part of the Serbian security structures has been more wishful thinking than reality.
Serb politicians have always denied Gen Mladic was on their patch. The truth was that, most of the time, they did not know whether he was or not, correspondents say.
In January 2006 the EU warned Serbia that its failure to hand over Gen Mladic could jeopardise talks paving the way for eventual EU membership.
It seems that with a new government in Belgrade, and a new head of Serbian intelligence, the heat on Gen Mladic is about to be stepped up.