The paper, citing unidentified people it said were familiar with the matter, said the two companies have been in "deep" talks for the past few weeks. Discussions are still at a sensitive stage, however, and could risk crumbling due to some last-minute issues, it said.
Nokia did not immediately return calls seeking comment.
"It makes a lot of sense," he said. "This is one of the areas that should become extremely important in the future. ... Nokia could very well build one of its core services around it."
Honko added that Chicago-based Navteq, which maintains digital maps and licenses them to global positioning systems and Web sites, is "the most significant player in its field."
A potential price tag could be as high as around EUR7 billion (US$10 billion), he said - something that would be Nokia's biggest acquisition to date.
Nokia shares fell 1.6 percent to EUR26.24 (US$37.21) in Helsinki, a drop Honko said could be attributed to investor worries that Nokia could be willing to pay too much for Navteq.