When he won the election, he was known as Kevin 07.
But in the 12 months since, his unrelenting work ethic has earned him the nickname Kevin 24/7, while his penchant for foreign travel has prompted others to call him Kevin 747.
According to the Sydney Daily Telegraph, he has travelled 160,000 km (100,000 miles) and has spent over 50 days out of the country.
So what has he got to show for his frequent flyer miles and infrequent breaks from work?
A high approval rating for one - an enviable 68% according to the latest survey of public opinion.
The polls suggest that Kevin Rudd is more popular now than he was this time last year, when he ended 11 years of conservative rule by promising risk-free change.
Judging by the polls, Australians appear to value his calm, deliberative approach to government and his unflashy style.
Traditionally, the country has favoured trusty technocrats over bold visionaries.
Certainly, it has been a year of great symbolic accomplishment. His deftly worded apology to Aboriginal Australians, the first act of the new parliament, carried incalculable cathartic power.
Similarly, the decision to ratify the Kyoto Protocol, his first act as prime minister, improved Australia's standing in the world - it drew a standing ovation from delegates at the UN Climate Change Convention in Bali.
The decision to terminate the Pacific Solution, the practice introduced by the Howard government which held asylum seekers at detention centres on remote Pacific islands, was both symbolic and substantive.
Again, it drew plaudits at home and abroad, and marked another definitive break from the past.
Still, Kevin Rudd has faced criticisms that he lacks political courage and that he has failed to map out a bold, reforming agenda.
Many critics would like to see him leverage his personal popularity and depart from his innate cautiousness. Efficient managerialism hardly stirs the soul.
"He's tremendously brave at big symbolic gestures when really the opposition has crumbled away," according to the author and journalist David Marr, a strident critic of the Howard government.
"The apology was a magnificent thing, but by the time he delivered it there was really no opposition to it any more.
"But whether he's got the courage to face big difficult decision when there's massive opposition that's what is left to be seen."
Perhaps his trickiest policy challenge is delivering an emissions trading system by 2010.
Environmentalists already fear he is backtracking, and will ultimately settle on unambitious emissions targets because of his fear of hitting the vital coal and energy sector.
Other than selecting a new Governor General, Quentin Bryce, who is thought to have Republican sympathies, he has done little to "accelerate the Republican agenda", which was an early promise.
That has disappointed his Labor predecessor, Paul Keating, who has complained that the Rudd government lacks an overarching narrative.
Mr Keating thinks Australia should ditch QE2 - as he calls the Queen - and that the failure to do so inhibits the development of a more overtly Asia-centric foreign policy.
"You can't get around in Asia saying 'by the way, we borrowed the monarch of another country, the Queen of Great Britain, as our head of state'," Mr Keating recently complained.
Another oft-heard criticism is that although Mr Rudd speaks fluent Mandarin he has not yet mastered plain English.
His speeches can be stultifyingly dull, peppered as they are with bullet points and acronyms. Annabel Crabb of the Sydney Morning Herald has memorably called him "the jargon hunter".
He also has an unhappy tendency to lapse into militaristic rhetoric. On Armistice Day, as Australia remembered its war dead, Mr Rudd launched a "war on unemployment", a rather jarring juxtaposition.
In parliament earlier this month, the opposition frontbencher Joe Hockey delivered one of the most effective sound-bites of the year when he reminded the prime minister that he had already launched "wars" on Japanese whalers, downloads, disadvantage, "pokie" machines, doping in sport and banking salaries.
"Prime minister, how goes the war on everything," Mr Hockey bellowed, to uproarious laughter from the benches behind.
Sure enough, Mr Rudd has likened the global economic downturn to a "rolling national security crisis", and knows that his political future will be determined by his economic stewardship rather than his political vision.
The immediate aim is to avoid Australia slipping into recession, something which he hopes to accomplish through massive public spending on major infrastructure projects, even if it means wiping out the government's budget surplus.
Curiously, his public standing has improved since the collapse of Lehman Brothers, even though in the new opposition leader, Malcolm Turnbull, he now faces a formidable opponent.
Every Australian prime minister since the war has won a second term in office, which is part of the country's conservative tradition.
The present occupant of the Lodge in Canberra is determined to extend that run.