Reinfeldt called Erdogan, who had previously cancelled a planned state visit to Sweden after the vote, to voice "his sadness and say that his government absolutely did not share the decision," Ankara said in a statement.
Blaming the vote on "domestic politics," Reinfeldt said his government was "ready to do the necessary so that this unfounded decision does not harm bilateral relations," according to the text.
The Swedish prime minister also assured Erdogan that the parliament's move did not weaken Stockholm's support of Turkey's EU accession ambitions.
Going against the government's advice, the Swedish parliament voted by a narrow margin on Thursday to recognise the "genocide of Armenians" and other ethnic groups, during the breakup of the Ottoman Empire.
Ankara quickly recalled its ambassador and cancelled a visit by Erdogan to Sweden after the vote, which came just days after a similar move by a US Congressional panel.
In remarks to Sweden's TT news agency, Reinfeldt said that he had expressed to his Turkish counterpart "regrets following the parliament's decision because it politicizes history."
According to the Turkish statement, Erdogan "strongly insisted on the disappointment" felt in Turkey over the vote, while recognizing that the government was against it.
He also called for "measures to repair the situation."