If Apple displaces Google from its preferred status on the smartphone, it would be perhaps the clearest sign of the growing tension between two Silicon Valley icons, which were considered allies in a common cause against Microsoft.
Talks between Microsoft and Apple have been going on for weeks, the article said, citing two people familiar with the matter. Negotiations might not conclude quickly and might still fall apart, the article said.
Microsoft and Google declined to comment. Apple was not immediately available for comment.
Microsoft's Bing search engine, which debuted last year, is trying to wrest market share from Google, the leader in Internet search.
Apple's rivalry with Microsoft dates back years, though they work together in certain areas of the software market.
In contrast, the Apple-Google rift is only emerging. The companies compete on a number of fronts, including operating systems and the fast-growing smartphone market.
Obviously with Google and Apple, they seem to be having some friction, said ThinkEquity analyst Vijay Rakesh.
Until recently, replacing Google with Bing would have been seen as unreasonable, but now such a move might be possible, said Oppenheimer & Co analyst Yair Reiner.
While Microsoft and Google pose similar threats to Apple, Google's budding success with Android and Chrome may represent more immediate dangers to Apple, which could push it into the arms of Microsoft, Reiner wrote in a research note.
Google and Apple have lived in friendly coexistence for years as each became leaders in their arenas. Google is the default search engine on Apple's desktop and laptop computers.
Their ties run deep. Google director Ann Mather was chief financial officer at animation company Pixar, while Apple founder Steve Jobs was CEO. Former U.S. Vice President Al Gore is an Apple board member and also a senior adviser to Google.
But Google Chief Executive Eric Schmidt resigned from Apple's board in August, even as Google increased its presence in Apple's markets.
Google has been gaining strong support from handset makers and operators with its Android mobile operating system. Earlier this month, the search giant unveiled its Nexus One smartphone, which will compete with Apple's iPhone.
Google recently agreed to buy mobile advertising company AdMob for $750 million, a company that Apple reportedly pursued. Apple bought AdMob competitor Quattro Wireless.
Apple is working on ways to manage ads displayed on its mobile devices, a move that would challenge Google's advertising business, the BusinessWeek article said.
Apple sees Android as a competitive platform driving competitive devices and it recognizes that Microsoft is desperate to gain search market share, said Clayton Moran, an analyst at Benchmark.
Microsoft, I'm sure, will give Apple favorable economics so strategically and financially it could make good sense for Apple, said Moran.
The terms of Google's deal with Apple are unknown, though browser toolbar deals in the PC world typically involve the search provider paying an upfront fee to the PC maker, said RBC Capital Markets analyst Ross Sandler.
The search provider makes the money back when PC users click on search ads.
IPhone searches using Google's search bar appear to return more standard, unpaid results than paid search ads, suggesting that Google might lose money on the deal, Sandler said.
For Microsoft to displace Google on the iPhone, they're going to have to be willing to lose more money than Google is losing, Sandler said.
Microsoft has invested hundreds of millions of dollars in its money-losing online business as it tries to gain an edge in Internet-based advertising markets.
They're both playing the same game, Sandler said of Microsoft's and Google's mobile plans. They both need to be there longer term, it's just a question of how much do you have to give up today in order to chip away at that longer term vision.
(Reporting by Gabriel Madway, Alexei Oreskovic, Sinead Carew and Franklin Paul, writing by Gabriel Madway and Yinka Adegoke. Editing by Derek Caney and Robert MacMillan)