The signing in Warsaw during the first visit to Poland by a Russia patriarch has been described by the churches as a historic act of reconciliation and the establishment of a bridge between the denominations.
The two nations have feuded for centuries and their ties are still marked by distrust.
"We appeal to our believers to ask for the forgiveness of wrongs, injustice and every evil committed against each other," the document said. "We are certain that this is the first and the most important step toward rebuilding mutual trust, which is a necessary element of a lasting community and full reconciliation between people."
The document was signed during a ceremony at Warsaw's Royal Castle by Russian Orthodox Patriarch Kirill and Archbishop Jozef Michalik, the Polish church's highest-ranking leader.
Shortly after the ceremony, a Russian judge convicted three members of the punk band Pussy Riot of hooliganism driven by religious hatred and sentenced them to two-year prison terms for a performance in Moscow's main cathedral that called for the Virgin Mary to protect Russia against Vladimir Putin.
During the trial, the band members apologized to all Orthodox believers, saying that they did not mean to offend anyone and that their performance was aimed against Putin and Kirill, who had urged Russians to vote for Putin.
But Kirill, who took Putin's side in the case, has not commented on the Russian court case or the verdict since arriving in Warsaw on Thursday.
The document that Michalik and Kirill signed mentions the "open enmity, even fighting between our nations" in the past and calls for a "brotherly dialogue" in all walks of life.
Church leaders said it is not another political declaration, but a religion-motivated call to the hearts and minds of ordinary people in both nations.
Kirill stressed that serving Christian religion obliged church leaders to promote the reconciliation.
Some have compared the document to a historic 1965 letter by Poland's bishops to the Catholic church leaders in Germany, offering and asking forgiveness for past wrongs between Poles and Germans, the most painful committed during World War II.
Today, Poland and Germany are enjoying friendly relations and are cooperating within the European Union.
The many sources of bitterness between Poles and Russians include Polish resentment over Moscow's control of Poland during the communist era and Russia's reaction to seeing Poland reject its influence and join Western institutions like NATO.
Elderly Poles still talk bitterly about Moscow's "stab in the back" — the attack from the East by the Soviet Red Army on Sept. 17, 1939, which came less than three weeks after German troops invaded Poland from the West, starting World War II. They point to the murders of more than 20,000 of their officers by Soviet secret police in 1940 in the Katyn forest and other sites.
More recently, conspiracy theories have smoldered since Polish President Lech Kaczynski and 95 other people were killed in a 2010 plane crash in Russia. Some Poles have accused Russians of not fully cooperating in investigating the crash.
Relations between the Orthodox church and the Catholic church also have been tense.
The Orthodox Church prevented Polish-born Pope John Paul II from making a trip to Russia.
The Orthodox also have accused the Vatican of seeking Catholic converts in traditionally Orthodox areas — a charge Rome denies.
Poland's official in charge of discussing the sticking points with Russia, Adam Daniel Rotfeld, said the document signed Friday also laid foundations for an improvement in relations between the two churches in general.