It is seen as a mandate to crack down on the Marxist insurgency fuelled by drugs money that has bedevilled South America's oldest democracy for 38 years.
The Oxford-educated lawyer will be sworn in on 7 August, provided the rebels do not kill him before then.
Guerrillas from the Revolutionary Armed Forces of Colombia (Farc) shot Mr Uribe's father, one of Colombia's wealthiest ranchers, in a bungled kidnap in 1983, and have made 15 assassination attempts against the right-wing president-elect.
Mr Uribe's experience as the mayor of Medellin, long a cocaine barons' fiefdom, and his record as a provincial governor in Antioquia have solid-ified his reputation as a hardliner who will not give in to rebels, who have about 22,000 fighters.His first-round election triumph is unprecedented and, as an independent, the bespectacled former governor shatters the political tradition of Colombia's two establishment parties alternating power every four years.
His closest rival, the former interior minister Horacio Serpa of the Liberal Party, trailed with 31.7 per cent of the votes. The Conservatives failed to field any candidate, after the peace process launched by their president, Andres Pastrana, was written off as an embarrassing failure.
Mr Pastrana's concessions to Farc and the smaller National Liberation Army (ELN)allowed heroin and cocaine production to soar, as did kidnappings and civilian deaths. The civil war entered the cities with a series of car bombs and kidnaps meant to increase funds with ransom payments.
After a demilitarised rebel safe haven was abolished three months ago, Venezuela, Panama, Ecuador and Brazil began reinforcing their borders against refugees fleeing the bloodshed.
Although younger voters in the cities defied rebel threats and queued in record numbers to choose between Colombia's 11 presidential candidates, abstentions were high in the countryside, where guerrillas dynamited power pylons, blocked roads and burnt ballot papers, despite the presence of 250,000 troops. Some 54 per cent of the 24 million registered voters stayed at home.
Despite campaign promises to double the armed forces, increase military spending, and to organise one million civilians into a vigilante militia, Mr Uribe's first gesture was surprisingly conciliatory. He urged a rebel ceasefire and called for international mediation. Farc has refused to lay down arms and negotiate.
"The violent ones have wasted many opportunities for peace - they will always have opportunities," he told cheering crowds in Bogota after the US ambassador, Anne Patterson, congratulated him.
The new President promised to reverse Colombia's international image "as one of the most violent nations in the world". Mr Uribe vowed to achieve security. "So [the rebels] don't kidnap the businessman, so they don't kill the labour leader, so they don't extort the rancher, so they don't force the peasant to flee his home," he said.
Colombia's conflict costs an estimated 3,500 lives each year, and has shown no sign of abating. "Strengthening the armed forces is the necessary way to protect civilians and for the complete recovery of human rights," Mr Uribe continued in his victory speech.
Innovative social policies, such as plans to convertcoca fields into rainforest and to secure loans for the unemployed to start businesses, have won praise for the president elect.
Mr Uribe was the clear favourite of the Bush administration and he is expected to ask Washington for increased aid.