Starting from fourth (Kevin) and 10th (Jenson), both drivers began the race on Pirelli's Option tyre; Kevin stayed fourth in the opening laps despite a scary sideways moment as he powered off the startline, and Jenson ran in 11th place after steering clear of the first-corner chaos.
Both drivers gained a position after Lewis Hamilton's retirement on lap 3. Jenson took full advantage of the race's Safety Car on lap 11, which was brought out to allow marshals to clear debris from the track after Valtteri Bottas brushed the wall at the exit of Turn 10. Jenson's pitstop was incredibly well timed, allowing him to duck in to the pitlane at the last moment on lap 11 to make his first stop (3.10s), switching to another set of Options. He fully capitalised on the situation to emerge sixth.
Kevin stopped a lap later - also under the Safety Car - and took on a set of Options (3.35s). Throughout the middle stint, both cars held position, Jenson sitting closely behind the battling Fernando Alonso, while Kevin maintained a steady gap to second-placed Daniel Ricciardo.
The team boxed Jenson early, on lap 32, to switch to Primes (3.31s), using the undercut to vault both Alonso and Nico Hulkenberg, and emerge fourth. He began to close down Kevin, but his slightly older rubber meant he ultimately held this position until the chequer. Kevin's second stop on lap 37 (2.93s, Primes) allowed him to narrow the gap to Ricciardo. He closed to within a second, but was just unable to pass the Red Bull driver. Nevertheless, as a result of Ricciardo's exclusion, Kevin's second-place finish makes him the most successful F1 rookie since Jacques Villeneuve managed the same feat in the 1996 Australian Grand Prix, also in Melbourne.
By virtue of getting both cars to the finish in high-scoring positions, McLaren now leads the constructors' championship.
Kevin Magnussen: "It's just fantastic to be on the podium! What happened today just feels surreal. Being on the podium in the first race of my Formula 1 career - it's amazing.
"My ‘moment' at the start was quite scary - I got on the power a bit too quickly, and nearly lost it. But the car was fantastic today - I was always able to place it exactly where I wanted, and I had the pace to fight the Red Bull. I had a bit of a go at Daniel towards the ends of the race, but didn't quite have the speed to get past.
"I want to say a big congratulations to the team for doing such a good job over the winter and for working so hard to prepare me for this - it's just crazy!
"Where do we go from here? Well, we need to continue improving. And I'm sure we will. I'll try to learn as much as I can, and to carry this experience forward to Malaysia. It's a completely different circuit, so there's no guarantee we'll have the sort of speed we showed here today, but I'm sure the team will keep pushing as hard as they've done already this year.
"I'm very happy, and I'm sure the guys are happy to be leading the constructors' world championship, as indeed I am too. That's a big boost, and the guys completely deserve it. Me? I'll just keep pushing as hard as I can."
Jenson Button: "It was a great drive by Kevin today - I had a lot of fun chasing him and Daniel down at the end of the race, but my tyres were several laps older than theirs, so it was always going to be tricky. Still, I had a good race - the car's balance wasn't quite right when I was in traffic - I struggled with understeer when I was behind people - but the car worked very well in clear air.
"For some reason, it seems to be more difficult to overtake now than it used to be, so we had to do it during the pit stops. During my second stop, we damaged the nose - which made it a bit cooler in the cockpit! - but the guys did a great job of putting me in the right place at the right time. When the Safety Car came out, I quickly dived into the pit lane at the last second - which gained me a couple of places. And then the second stop gained me a couple more. They were both great calls.
"As a team, I think we can be very proud of the job we did today. I don't think we expected to be leading the constructors' world championship at the end of this weekend, but I think the pace in the car is generally there: in clear air, we seem capable of fighting every team except one. I'm really looking forward to getting back in the car in Malaysia.
"It's been an emotional day for me, but it's been great to have my sister, my fiancée and lots of friends around me, so that definitely helped."
Eric Boullier, Racing Director: "To be in first place in the constructors' world championship is a very nice feeling, but let's not forget that today's race was only the first of 19, and I'll be a lot happier if we're still in first place in the constructors' world championship after the 19th race!
"Having said that, I'm not making any predictions, and it's clear that we've got a lot of work to do in order to close the performance gap between our car and the fastest car.
"Kevin scored 18 of the 33 constructors' world championship points we racked up today, Jenson 15, and both guys drove superbly.
"Indeed, Kevin's drive was one of the finest performances by a Formula 1 rookie in living memory. Despite his youth and inexperience, he drove like a man who'd notched up 100 grands prix already. It was a complex and challenging race, yet he managed those complexities and challenges faultlessly.
"Jenson recovered skilfully from his disappointing qualifying result, which was the result of his not being able to put in a final quick lap owing to inopportune yellow flags, and drove the sort of measured yet combative race that he's become famous for.
"Finally, I want to give a huge amount of credit to the guys, not only here in Melbourne but also in Woking and Brixworth, who have done such sterling work to deliver such a solid and reliable car for Kevin and Jenson to race here today.
"Our next stop is Malaysia, which will be hot and hard. But we're ready for the challenge."
Check out our race gallery, here.