Erdogan vowed to pursue a period of reconciliation in Turkey after securing the post with more than 52 percent of the vote on Sunday.
"The president praised the prime minister’s speech on Sunday and noted that as Turkey’s first directly elected president, the prime minister has an historic opportunity to further move Turkey forward," the White House said in a statement.
"The president and prime minister agreed on the importance of close cooperation on Syria and Iraq and the terrorist threat emanating from the region," the White House said.
The call lasted 45 minutes, according to Turkish sources.
Erdogan last month acknowledged strains in his relations with Obama, saying he no longer spoke directly to the U.S. president as he had in the past.
Erdogan’s leadership style, from his bombastic rhetoric on Israel to his crackdown on anti-government protests last summer, has raised increasing concern among Western allies in recent years.
But Turkey remains a key member of the NATO military alliance and a strategic ally for Washington in the turbulent Middle East, with common interests including energy security and the fight against terrorism.