Karamanlis's role in compromise talks with Turkey began a process of weakening in the ERE's electoral support that continued into the early 1960s. At the same time, elder statesman Georgios Papandreou's coalition profited from public disaffection with Karamanlis to revive the center-left after decades of suppression.

The first sign of deterioration in the conservative party's position came in the 1958 parliamentary election. The ERE lost seats as the United Democratic Left (Eniea Dimokratiki Aristera-- EDA), ally of the outlawed communist party, gained the secondhighest vote total. Seeking validation of his pro-Europe policies and the Cyprus treaty, Karamanlis asked for new elections in 1961. His ERE party recovered somewhat from the 1958 result by obtaining 51 percent of the vote and 176 seats in parliament. Former Prime Minister Georgios Papandreou and his Center Union, (Enosis KentrouEK ), in association with some smaller centrist parties, finished second with 34 percent of the vote and won 100 seats. The EDA finished third with 15 percent and 24 seats.

The 1961 election was marred by widespread allegations of tampering and corruption. Army and police units, alarmed by the high procommunist turnout in 1958, openly intimidated voters, especially in areas known for their left-wing sympathies. Although Karamanlis likely played no role in the voting irregularities, Papandreou found an issue to rally the people: he charged electoral fraud and demanded that the elections be declared void. When they were not, he committed himself to a "relentless struggle" to ensure free and fair elections in Greece.

Many people had grown weary of the stifling of the left, which had continued since the end of the war. Many leftists were still in prison, internal security forces continued to wield great influence, and advancement in the civil service and the military remained dependent on political affiliation. In short, people were tired of the suppression of personal freedoms. In the early 1960s, political violence increased, as exemplified by the 1963 assassination of EDA deputy Grigorios Lambrakis by thugs connected to the security forces (an event dramatized in Costa Gavras's film Z).

Karamanlis felt his support deteriorating both to the left and to the right. He clashed with King Paul and Queen Frederika on a number of issues, especially the relationship between the monarch and the military. Karamanlis also became convinced that the power of the military was inappropriate for a democratic state. Once more the constitutional question regarding the role of the monarchy was rising to the surface of Greek political life, and, as in the past, it inevitably involved the armed forces as well. Finally, in early 1963 Karamanlis yielded and tendered his resignation. Upon its acceptance, he went into self-imposed exile in Paris.