On Monday Mr Kilman was able put together a coalition from the 16 political parties and four independants, who won seats in the 52 seat parliament.
But the MP's who make up the new opposition have vowed to fight his elecction, and have not ruled a pre Christmas challenge.
Pacific Correspondent Campbell Cooney reports.
Speaker:Ralph Regenvanu, Vanuatu MP.The Editor of the Vanuatu Independant Tony Wilson
COONEY: While Sato Kilman was able to get the numbers to be re-elected as Vanuatu's Prime Minister, his grip on the office is tenuous.
His party won only six of the 52 seats on offer, and currently there are 16 political parties in that parliament from which Mr Kilman has formed a coalition, with at least on of the parties now in opposition holding more seats in their own right.
The Editor of the Vanuatu Independent Tony Wilson says the win is a demonstration of Mr Kilman's negotiating skills.
WILSON: Obviously he's very, very proficient at number counting and number crunching and persuading MPs that he is the way to go. The sad news for the people of Vanuatu is that given the state of things it's highly unlikely that we'll see that government in situ for the next four years. We can probably now expect to see perhaps even a number of changes where MPs are persuaded for various reasons to switch camps.
REGENVANU: I think it's a disappointing result for almost all of Vanuatu. I don't think many people wanted to see this old government get back in. It's unfortunate that our side was not able to maintain the numbers. But we're hoping that we can change that situation soon.
COONEY: Ralph Regenvanu is one of the successful candidates in the Port Vila constituency, and his newly formed Ground and Justice Party had a strong turn out in the polls.
He says that the first challenge to Sato Kilman's leadership could be launched before the end of the year.
REGENVANU: The MPs have an induction workshop starting tomorrow for three days, all the new MPS, and some of us old MPs will be attending as well of course. And the budget is yet to pass so I doubt that that will happen this year because recess is 20th of December. If the opposition decides to put a motion of no confidence in the Prime Minister, they have until the 20th of December to do that as well, which means it has to go in in the next couple of weeks to qualify for the notice time. And we'll see how we go from there.
COONEY: So that challenge could happen anytime soon?
REGENVANU: Anytime soon, yes.
COONEY: Is that likely?
REGENVANU: I think it is likely yes.
COONEY: Amongst those MP's supporting Mr Kilman are veteran MP's George Wells, who will be his Speaker of parliament, and another former PM Ham Lini, will return as his deputy prime minister.
Also in his cabinet are Alfred Carlot and Marcellino Pipite, who are still facing charges they illegally boarded a super yacht, Phocea, before it had been processed by customs.
But Tony Wilson says the return of so many veteran MP's, some of who remain under a cloud, has many in Vanuatu scratching their heads.
WILSON: It seems likely that we're going to see a significant change and that didn't happen. Part of the problem is that a lot of this country is still terribly isolated in terms of communication. So the people in the outer islands have no radio, have no real communications, they have no way of knowing what their representatives in parliament are actually doing or not doing. And each election these people return to their islands, often it's the only time they've been seen since the last election, and they come with the promise of bush knives and glass covers and solar panels, which are gratefully accepted by the people in the villages in these islands who think that's what an election is all about. Well it's common knowledge last year particularly that the government budget was something in the vicinity of 50 per cent short of what it should have been to operate, and we had crazy scenes where as recently as about six weeks ago we ran an advertisement in our weekly newspaper from the Department of Education telling everybody that they'd run out of money. In fact we actually had a debate at the newspaper as to whether we'd take the ad because there was some worry about who was going to pay for it.