Gul was invited by Armenian President Serzh Sarkisian to watch an international football match between their national teams, with an extended closed-door session before the two leaders headed across town for the World Cup qualifier.
The Turkish team went on to win the match, 2-0.
Two deeply felt issues have long separated Armenians and Turks. The first are the mass killings of ethnic Armenians around World War I, which Armenia and some other countries call genocide; anyone referring to them that way in Turkey faces criminal prosecution. The other issue is Armenia's support of Nagorno-Karabakh in Azerbaijan, where Ankara accuses Armenia of occupying part of the territory of one of Turkey's closest allies. Armenia says it is helping its ethnic kinsmen defend themselves.
The visit offered the rarest of opportunities for a review of bilateral ties, something that made it more than a symbolic gesture. The two states do not have diplomatic relations.
Gul is the first Turkish head of state to visit Armenia since it became independent from the Soviet Union in 1991.
Reuters quoted Gul aboard the plane en route to Armenia as praising Sarkisian for his "brave" decision to invite him to the game. Gul was booed and hissed by fans when he entered the stadium for the evening match.
The initiative has virtually assured a second landmark event, since at the end of their private meeting, Gul invited Sarkisian to the next match between their national teams in Turkey.
Sarkisian declared that there is now the "political will to decide the questions between our countries, so that these problems are not passed on to the next generation."
Speaking ahead of his eagerly anticipated arrival in Yerevan, Gul had said he hoped the match would help lift the barriers dividing two people "who share a common history and will contribute to regional friendship and peace."
RFE/RL Armenian Service correspondent Ruzanna Stepanian said hundreds of supporters of the Armenian Revolution Federation party -- a member of the governing coalition -- greeted Gul's motorcade from Yerevan airport with placards reading "No to genocide" and "Accept the truth." The party continued its protest with a candlelight vigil near the stadium where the two teams square off, at a memorial to the Armenian victims of the mass killings early last century.
A major opposition alliance headed by ex-President Levon Ter-Petrossian endorsed Sarkisian's initiative and chided the Armenian Revolution Federation party's protest as "illogical," given its participation in the government. Ter-Petrossian's bloc postponed a major political rally it had planned for September 5, citing the historic nature of the Turkish visit.
The "Turkish Daily News" quoted diplomatic sources as saying the agenda of the meeting between Gul and Sarkisian would include bilateral relations and Ankara's proposal to set up a joint committee of historians to study the massacre of Armenians under the Ottoman Empire during World War I.
Analysts say Yerevan's hope is that a thaw would lead to a permanent reopening of the Turkish-Armenian border, which has been closed for 15 years.
Ankara's interest in a detente is seen as part of a larger Turkish strategy of stabilizing relations with its bordering states, including Greece, Syria, Iraq, and now Armenia.
"My president's visit to Yerevan...is going to be an important step to open doors for dialogue with Armenia," Foreign Minister Ali Babacan told Reuters.
The overture came quickly on the heels of Russia's cross-border military operations to back separatists in Georgia and Moscow's subsequent recognition of their independence, a situation that Babacan has described as "alarming."
Babacan said the war between Russia and Georgia dislodged a series of frozen conflicts in the Caucasus, raising risks of further instability but also creating opportunities for new diplomatic efforts to resolve them.
"The current circumstances, we believe, are conducive for such a bold step [as the bilateral visit]," Babacan said in an interview late on September 5 in Avignon, France, where he was attending a meeting of EU foreign ministers.
Babacan said the fighting in neighboring Georgia "showed we need to come up with a fresh approach to resolution of conflict in the Caucasus."
The minister rejected Turkish opposition criticism of the rapprochement with Armenia, saying it was time for "more open views."
RFE/RL Armenian Service correspondent Emil Danielyan said full-page advertisements placed by four local companies in many Armenian newspapers on September 6 welcomed the Turkish leader to their country and urged the "honorable Mr. President Abdullah Gul" to keep hopes of a diplomatic thaw alive after the football match-up by "play[ing] beyond 90 minutes."
* Modern Armenia is a small, landlocked country on Turkey's eastern border. The ancient kingdom of Armenia, at its peak, stretched from the Mediterranean to the Caspian seas, and included much of the territory of modern Turkey.
* The Muslim Turkish Seljuk and then Ottoman empires ruled Armenian regions from the 11th century until the collapse of the Ottoman Empire during World War I. The territory that is now modern Armenia was seized from Persia by Russia in the 19th century, was briefly independent following World War I, but was annexed by the Soviet Union in 1920.
* After the foundation of the Republic of Turkey in 1923, ethnic Armenians in Turkey became an officially recognized minority like Jews and Greeks and were allowed to run their own schools.
* The border between Turkey and Armenia has been closed for 14 years because of a dispute between Turkey's ally Azerbaijan and Armenia over the territory of Nagorno-Karabakh.
* During World War I, thousands of Armenians were marched from the Anatolian borders toward Syria and Mesopotamia (now Iraq) and Armenians say some 1.5 million died either in massacres or from hunger and thirst in the desert.