Operation Sovereign Borders is partly about turning back boats with asylum seekers on them but it's also about discouraging asylum seekers, with the prospect of resettlement in Papua New Guinea.
It was former Prime Minister, Kevin Rudd, who stitched up the deal with PNG's Prime Minister Peter O'Neill, but it's Tony Abbott who is now depending on Mr O'Neill to stay the course and help him stop the boats as he's promised again and again.
But there's more to the PNG relationship than just asylum seekers.
Presenter: Liam Cochrane
As Australia gets used to it's new Government, so too does it's closest neighbour, beginning with Papua New Guinea's Prime Minister Peter O'Neill.
PETER O'NEILL: "On behalf of the people of PNG, let me take this opportunity to congratulate Tony Abbott and the Liberal Party for their resounding win in the Australian elections. Of course we look forward to working closely with them."
Paul Barker from the Port Moresby think tank the Institute for National Affairs says it's important those at the top get along.
PAUL BARKER: "Really it will be crucial for the two PMs and for other members of the Government in PNG and Australia to establish that relationship early on and really know where the Abbott Government is going to be coming from."
Tony Abbott has visited Papua New Guinea - to walk the Kokoda Track in 1980 - but incoming Foreign Minister Julie Bishop has been a frequent visitor in more recent times.
JULIE BISHOP: "Within the Pacific, there is no more important relationship for Australia than with Papua New Guinea."
PNG's High Commissioner to Australia Charles Lepani says Julie Bishop has worked hard to make the right regional connections.
CHARLES LEPANI: "Foreign Minister-elect has had a lot of experience in Papua New Guinea, has gone there a lot of time and met all our leaders, most of our leaders and knows a fair bit about the country."
Papua New Guinea's prominent role in Australia's offshore processing of asylum seekers will be a key bilateral issue... and one that gives PNG considerable diplomatic leverage.
Tony Abbott's Coalition Government will retain much of the system set up by Kevin Rudd - detaining asylum seekers who arrive by boat, sending them to PNG's Manus Island... and looking to resettle those found to be genuine refugees within Papua New Guinea.
TONY ABBOTT: "As soon as we are sworn in, we'll commence Operation Soveriegn Borders. That will start making a difference from day one. Yesterday I spoke to Prime Minister O'Neill of PNG. We will certainly make full use of the opportunities available for offshore processing at Manus island."
Alongside the issue of asylum seekers... another sometimes-sensitive subject is foreign aid.
Papua New Guinea is currently Australia's second biggest recipient of development assistance... an estimated 507 million Australian dollars in the current financial year... but the Tony Abbott has promised a more austere future..
TONY ABBOTT: "At the moment we are borrowing money from overseas to send money overseas in aid. It doesn't make a lot of sense. We're not cutting foreign aid, we're simply reducing the rate of growth."
Whether it's called a cut or a reduction in growth... the Government hopes the move will save 4.5 Billion dollars over four years.
PNG's top diplomat in Australia, Charles Lepani, is taking a positive view, especially in light of a huge Liquid Natural Gas pipeline that's about to start flowing.
CHARLES LEPANI: "It's a natural course of events, a government should expect aid to continue decline and less dependence from Papua New Guinea. With our LNG project coming on stream, we expect the issue of self-sufficiency from aid will be a major focus of our government and future discussions with the Australian Government."
In fact there are plenty for the two nations to discuss... there's trade and investment... there's the prospect of Australian police officers training PNG police... there's the concern of tuberculosis spreading south...
... and there's Tony Abbott's idea to revive the Menzies-era Colombo Plan... which Charles Lepani says will be a great idea.
CHARLES LEPANI: "The Colombo Plan is also meant to extend to PNG. It's to be an exchange arrangement for students from Papua New Guinea to Australia and from Australia to Papua new Guinea.. studying and getting to know each."
There is, also, a darker side.
Corruption is rife in PNG and there have been uncomfortable allegations of corrupt Papua New Guineans using Australia as a place to launder money and spend their ill-gotten gains.
But if Julie Bishop really wants to be a popular Foreign Minister in PNG, there's one issue that's sure to please the rugby-mad nation...
JULIE BISHOP: I have even raised the Holy Grail for PNG - a national team in our NRL - with the former CEO David Gallop and with the PNG NRL bid team - yes one exists, a PNG NRL bid team. But we should not underestimate the bridges that would be built through sporting links with our close neighbour.
Sport, aid, corruption, asylum seekers, law enforcement, health, education - there's plenty on the diplomatic agenda for Papua New Guinea and the new Australian Government.