With Australia cruising at 0-60 chasing the Proteas' 8-296, Maharaj wreaked havoc during a stunning spell as the hosts lost 6-29 in 55 balls at Cazaly's Stadium.
The 35-year-old bowled his 10 overs unchanged - at one stage having 5-9 - to finish with 5-33. It was the first five-wicket haul of his ODI career and was aptly named player of the match.
Maharaj's efforts were the fourth-best ODI numbers by a South African bowler in Australia.
"In the T20s, coming off a similar wicket, there was a little bit of turn as the game went on," Maharaj said.
Debutant Prenelan Subrayen, a right-arm offspinner, started Australia's collapse by getting the dangerous Travis Head stumped for 27.
"My life was made easier when Prenelan got the first wicket, he bowled exceptionally well on debut," Maharaj said.
"I just tried to utilise the conditions and use the angles of the crease and fortunately enough, I got the reward."
Captain Mitch Marsh played a lone hand from the top as none of Australia's middle-order reached double figures.
While Marsh remained at the crease, Australia had an outside chance of pulling off a remarkable win.
But when Marsh fell for 88 to Nandre Burger (2-54), it was only a matter of time before the Proteas secured victory and bowled Australia out for 198 in the 41st over.
"Keshav's an outstanding bowler, and certainly a little bit more spin than we expected," Marsh said.
"At times you have to give your hats off to someone like him, he won them the game."
Spin, unexpectedly, dominated in Cairns, after Travis Head's part-timers also proved hard to handle.
Australia's aggressive opening batter took 4-57, claiming opener Ryan Rickelton (33), as well as Tristan Stubbs (0) and rising star Dewald Brevis (6) within three balls.
The Proteas need no reminder of Head's bowling capabilities after he took two crucial wickets in Australia's thrilling World Cup semi-final win in 2023.
Rickelton made a productive start with World Test Championship final hero Aiden Markram, the pair putting on 92 for the opening wicket.
Markram (82) played flawlessly for his first 80 balls, but fell to a stock-standard delivery from Ben Dwarshuis (2-53) when seemingly headed for a fourth ODI century.
WTC-winning captain Temba Bavuma returned for his first match since the historic final at Lord's two months ago, crafting a patient 65 before being bowled by Dwarshuis when trying to lift the run-rate with four overs left.
Allrounder Wiaan Mulder, fresh off his extraordinary 367 not out in a Test against Zimbabwe last month, delivered in the final overs with a blazing unbeaten 31.
Earlier, South Africa suffered a major blow, losing spearhead Kagiso Rabada for the three-match series.
The 30-year-old will miss the 50-over games in north Queensland due to an ankle injury.
Australia fielded first after captain Mitch Marsh won the toss and elected to send the Proteas in to bat.
When captaining Australia, Marsh has won the toss 21 times and chosen to field every time.
Australia opted to play Alex Carey as a specialist batter, electing to use Josh Inglis as the wicketkeeper instead of their Test gloveman.
But Carey and Inglis both fell to Maharaj, playing poor shots to get out.
The second ODI will take place in Mackay on Friday.
18°C