The French capital is tipped to stage 2024 while the Californian city has hinted that it was prepared to wait four more years.
Paris and Los Angeles were the remaining candidates for the 2024 Olympics, a contest that IOC boss Thomas Bach said created "a golden opportunity".
The Olympic movement has had increasing trouble attracting prospective hosts given the soaring costs and taxpayer support required.
Paris and Los Angeles mounted progressive, exemplary bids that would trim expenses by using existing facilities, the IOC said, making clear that it did not want to reject either candidate.
Bach lobbied for a double hosting plan, which won unanimous approval from IOC members at a meeting Tuesday in Lausanne.
The IOC boss called the decision "historic".
"Ensuring stability of the Olympic Games for 11 years is really something extraordinary," he told reporters shortly after the plan was approved.
Two month window
The IOC now has a two-month window to negotiate with Paris and Los Angeles over which city will go first.
Bach said he wants a "tripartite agreement" before the IOC's main annual meeting in Peru's capital Lima on September 13th, when a vote on the 2024 host had been scheduled.
Immediately after the deal was approved, Los Angeles Mayor Eric Garcetti and his Parisian counterpart Anne Hidalgo appeared on stage arm-in-arm to thank the IOC members, leaving little doubt that a three-way pact was achievable.
Speaking later alongside Bach, Garcetti and Hidalgo voiced full confidence in the upcoming talks.
"I now know that I am sitting up here with two mayors, from two cities that will host after Tokyo the next two Olympics," Garcetti said, referring to the 2020 Games in Japan.
Hidalgo assured that "the Games will return to Paris".
Paris 'ready', LA to wait?
Bach said the negotiations would begin immediately, possibly over glasses of wine on Tuesday, adding an agreement could be announced next month.
In the highly unlikely event that there is no deal, the IOC will vote in Lima on 2024 alone, as initially planned, Bach said.
Delegations from the two cities -- led by French President Emmanuel Macron and Garcetti -- were in Lausanne making fresh pitches to IOC voters.
Paris has maintained a tougher line on the 2028 question, insisting it was focused on 2024, the centenary anniversary of the city's last Games.
READ ALSO: IN PICS: Macron visits Lausanne
"I am here to convey a message to say our people are ready to host these Games," Macron told reporters on Tuesday.
"After three failed bids we don't want to lose a fourth one," he said.
Paris mounted losing bids for the 1992, 2008 and 2012 Games.
The Los Angeles team has done did little to quell speculation it was open to 2028, with bid chairman Casey Wasserman reminding that the city had never given the IOC "an ultimatum" on the 2024 question.
The city last hosted the Games in 1984.
"Working hard to get the Olympics for the United States (L.A.). Stay tuned!" President Donald Trump said in a tweet, without making reference to a particular year.
'Great' Olympic cities
The Olympic movement has been stained by Games that erected grand multi-million dollar facilities that were left to crumble and rot, while the billions spent in public money offered no long-term benefit to host communities.
Los Angeles has stressed its near entire reliance on private funding while vowing to use the Games to broaden access to sports, something it won praise for doing following the 1984 edition.
While Paris has equally focused on leaving a positive legacy, Macron also highlighted the opportunity for France to rally around the "Olympic values" of tolerance and inclusivity, saying they were embedded in the country's "DNA."
"It truly is a tale of two great Olympic cities," said a report released last week by the IOC's 2024 Evaluation Commission.
Bach called their presentations on Tuesday "mind-blowing."