Newcastle - Zimbabwean-born David Pocock will captain a Wallabies side featuring five new caps while their opponents Scotland will also have plenty of new faces, having made six changes and named three new caps since their Six Nations defeat to Italy in March.
Pocock, who takes over from the injured James Horwill, will lead an Australian side on Tuesday also containing two New Zealand-born backs - Reds' Mike Harris and the Melbourne Rebels' Joe Tomane - who will debut at inside centre and wing respectively.
The other new caps are Reds fullback Luke Morahan, Waratahs blindside flank Dave Dennis and Brumbies prop Dan Palmer. A sixth player could potentially make a Test debut, with openside flank Michael Hooper named on the bench.
The selectors opted to go with the Waratahs' Berrick Barnes at flyhalf ahead of the Reds' Quade Cooper, who has played just 120 minutes since returning from knee surgery following last year's Rugby World Cup.
Australia coach Robbie Deans said Barnes's experience, his recent play in the position for the Waratahs and his background with the bulk of the group would be critical assets for the side given the short preparation time.
"Most of the players involved have either had plenty of previous background with us, or trained with us last week, so the combinations do have some history," Deans said.
Lock Nathan Sharpe will make his 102nd Test appearance, becoming the third-most capped Wallaby (level with Stephen Larkham but behind George Gregan's international Test-leading mark of 139 and George Smith's 110).
Australia will play Wales in the first of three Tests next Saturday in Brisbane. Deans said selectors kept that in mind when choosing the team to play Tuesday.
"With another Test to follow, four days after Scotland, and given the injuries that we've had to deal with around assembly, it wasn't practical just to base the side for Newcastle around the players who have been able to be with us for all of this last week," Deans said.
"We've effectively had to select two combinations to win two Test matches at the same time, although we will obviously assess how we come out of Tuesday night's game before finalising our line-up for the first Wales match."
The Wallabies are expected to name their team for the first Wales match on Thursday.
Ten of the starting 15 Wallabies for the Scotland Test were rested from the weekend's Super Rugby round. The Reds, who provided seven of the starters, and Force, who have two - Sharpe and Pocock - had 15th-round byes.
Among those who will back up are two Brumbies - debut winge Joe Tomane and hooker Stephen Moore. They played in the Brumbies' 27-19 win over Melbourne on Friday.
On Saturday, Scotland moved a few hours up the F3 freeway from their training base at Manly in Sydney to the predominantly industrial town of Newcastle for the Test. When they arrived, they announced wholesale changes to the side that finished the Six Nations in last place, including a 13-6 loss to Italy in Rome.
Glasgow prop Ryan Grant will make his debut in Newcastle, while uncapped players Tom Brown (outside back) and Tom Ryder (lock) have been named on the bench.
Omitted from the Scotland team that lost to Italy are Jon Welsh, Geoff Cross, Jim Hamilton and David Denton in the pack and Max Evans and Graeme Morrison in the backs.
They are replaced by Grant, Euan Murray, Al Kellock, Alasdair Strokosch, Joe Ansbro and Scott respectively. In a positional switch, John Barclay will move from blindside flank to No 8.
"We were all very disappointed by the results in the Six Nations championship and this tour is about our strong collective determination to put that right, play with confidence and win back pride," Scotland coach Andy Robinson said.
"There's been an intensity to training since we've been out here which has pleased me but, as ever, it's about delivering a consistent 80-minute performance and eliminating the sort of errors that have cost us dearly if we are to beat Australia."
There are eight players from the side which beat Australia 9-8 at Murrayfield in 2009, including Ross Ford as captain.
"When we last played Australia three years ago, it was one of the most courageous performances of scramble defense I have ever seen," Robinson said. "Four times, Australia were over our line only to be held up and it will require that uncompromising resolve in Newcastle on Tuesday if we are to repeat that success."
Scotland have played 10 Test matches in Australia and it has been 30 years since their last win - at Brisbane's Ballymore in 1982.
15 Luke Morahan, 14 Joe Tomane, 13 Anthony Fainga'a, 12 Mike Harris, 11 Digby Ioane, 10 Berrick Barnes, 9 Will Genia, 8 Scott Higginbotham, 7 David Pocock (captain), 6 Dave Dennis, 5 Nathan Sharpe, 4 Sitaleki Timani, 3 Dan Palmer, 2 Stephen Moore, 1 James Slipper
Substitutes: 16 Saia Fainga'a, 17 Ben Alexander, 18 Rob Simmons, 19 Michael Hooper, 20 Nick Phipps, 21 Pat McCabe, 22 Adam Ashley Cooper
15 Stuart Hogg, 14 Joe Ansbro, 13 Nick De Luca, 12 Matt Scott, 11 Sean Lamont, 10 Greig Laidlaw, 9 Mike Blair, 8 Ryan Grant, 7 Ross Ford (captain), 6 Euan Murray, A5 lastair Kellock, 4 Richie Gray, 3 Alasdair Strokosch, 2 Ross Rennie, 1 John Barclay
Substitutes: 16 Scott Lawson, 17 Jon Welsh, 18 Tom Ryder, 19 Richie Vernon, 20 Chris Cusiter, 21 Duncan Weir, 22 Tom Brown