In a front page story, the Sydney Morning Herald said the new permanent military presence had been under consideration for some years as Washington looks to boost its Pacific Command.
The US currently has only a limited deployment in longstanding ally Australia, including the Pine Gap Joint Defence Facility spy station near Alice Springs, and the move would represent a significant geo-strategic shift.
Pentagon spokesman George Little declined to comment on the report, saying only: "Australia is an American friend and ally, and we will continue to work together to foster even stronger military ties with one another."
Obama arrives in the country on Wednesday, visiting the capital Canberra before becoming the first US president to travel to the Northern Territory when he lands in Darwin.
The US will not be building a new base in the city, but instead will reportedly use the existing Robertson Barracks nearby.
The facility is currently home to some 4,500 Australian soldiers and will need to be expanded to cater for the US Marines, the paper said, citing sources who declined to detail how many troops or sailors would be rotating through.
The Australian also reported the move, saying that other locations for a US presence were also possible, such as Perth in the west.
The plan would intensify the military alliance between the two countries, which is celebrating its 60th anniversary and has played a crucial part in anchoring the American influence in Asia.
Federal cabinet minister Tony Burke would not confirm or deny the reports.
"Can't confirm it. I don't know the answer to your question," he told the Seven Network, while Trade Minister Craig Emerson also would not comment when asked on Sky News.
US Marines are already based at Okinawa in Japan and on Guam as America's chief combat force in the Pacific theatre, and analysts said the Australian move was largely a response to the rise of China.
Beijing is boosting its military spending and capabilities, and becoming increasingly assertive on the high seas where it claims sovereignty over essentially all of the South China Sea, a key global trading route.
Just weeks ago, China sent its first aircraft carrier on its maiden sea trials, underlining the scale of the country's naval ambitions and sending jitters through Washington and Tokyo.
"China looms very large for both Australia and the US," said Professor Geoffrey Garrett, chief executive of the US Studies Centre at the University of Sydney, adding that the US strategy had two elements.
"The first concerns strengthening America's alliances and friendships in the region as an insurance policy that China's until now very peaceful rise changes course," he told AFP.
"The second is trying to build a regional economic architecture for the Asia-Pacific based on the market principles of America and Australia that China over time will have powerful incentives to join, even if this entails domestic reforms it has been unwilling to undertake up until now."
Andrew Shearer, a former senior diplomat at the Australian embassy in Washington, said India's rise also played a part.
"Everyone draws the China connection but it's as much to do with the rise of India as well. It's not all about defence, but to be able to conduct disaster relief, counter piracy and keep shipping lanes free," he told AFP.
"China certainly comes into their thinking, but it's not all about China," said Shearer, the director of studies at the Lowy Institute for International Policy.