All participants at the first Grand Slam of 2022 must be vaccinated against Covid-19 or have a medical exemption, which is granted only after assessment by two panels of independent experts.
Djokovic's triumphant Instagram post seemed to end months of speculation about whether he would be able to defend his Open title, and have a shot at securing an unprecedented 21st Grand Slam.
But instead of a conquering champion's return, Djokovic never made it past border control.
Australian border officials questioned the sports star and revoked his visa citing a failure to "provide appropriate evidence to meet the entry requirements".
Djokovic was held at the airport overnight and eventually moved to an undisclosed government facility pending deportation.
Legal sources told AFP that a deportation order had been scheduled for just after midday local time (0100 GMT), but a delay seemed likely pending Djokovic's possible appeal.
'Justice and truth'
News that Djokovic had received an exemption to arrive in Australia without being vaccinated was met by public outcry.
Australians have been unable to travel or welcome family from overseas for much of the last two years.
Stephen Parnis, a former Australian Medical Association vice-president, said the exemption sent an "appalling message" to people trying to stop the spread of Covid-19.
But the Serb's treatment on arrival prompted fury among his fans and a fiercely worded diplomatic rebuke from Serbia's president.
"The whole of Serbia is with him and... our authorities are undertaking all measures in order that maltreatment of the world's best tennis player ends as soon as possible", President Aleksandar Vucic said after speaking with Djokovic over the phone.
"In line with all standards of international public law, Serbia will fight for Novak Djokovic, justice and truth."
Djokovic's father echoed that nationalistic tone, claiming his son had been "held captive for five hours" at Melbourne airport and should return home to a hero's welcome.
"This is a fight for a libertarian world, this is not just a fight for Novak, but a fight for the whole world," he told the Russian state-run Sputnik media outlet in Serbia.
Sanja, a 35-year-old Serbian-Australian Djokovic fan had been looking forward to seeing him play in Melbourne.
"He went through a civil war to play tennis, he's done nothing wrong to the world. If this was Nadal or Federer there wouldn't be this much hype about it."
'No special favour'
Australia's leaders -- wary of public sentiment and mounting Covid problems ahead of an upcoming election -- pointed fingers over who was responsible for the saga.
Home affairs minister Karen Andrews said the government made "no apologies" for protecting the border, despite the prime minister earlier suggesting it was up to Melbourne officials and Tennis Australia.
"Individuals who do not meet our strict requirements will be denied entry to Australia, it does not matter who they are," she said in a statement.
Australian Open chief Craig Tiley said the defending champion had been given "no special favour" but had urged him to reveal why he got the exemption to soothe public anger.
Among the conditions allowing entry without a vaccine is if a person has had Covid-19 in the past six months. It has not been revealed if that was the case with Djokovic.
Tiley said just 26 of the approximately 3,000 players and support staff travelling to Australia for the tournament had applied for a vaccine exemption. Only a handful had been successful.
He defended the integrity of the exemption application process.
"Any person who met those conditions has been allowed to come in. There's been no special favour. There's been no special opportunity granted to Novak," Tiley said.
Djokovic voiced his opposition to the Covid-19 vaccine in April 2020 when it was suggested they might be obligatory so tournament play could resume.
"Personally I am not pro-vaccines," said Djokovic at the time. "I would not like it for someone to compel me to be vaccinated so I can travel."
During Djokovic's questioning at the airport, his coach Goran Ivanisevic posted a photograph on Instagram of himself and the Serb's other backroom staff, patiently waiting at the airport for a resolution.
"Not the most usual trip Down Under," wrote the former Wimbledon champion.