Turkey’s omnipresence at the margins of Europe throughout history has given shape to both Turkish and European identities. This paper sheds light onto this relationship by endeavoring to go beyond the much studied institutional relationship between Turkey and the European Union (EU). It focuses on three critical historical moments, namely the inter-war years, the years of labor migration after 1960, and the period after 2004 which began with the failure of the United Nations proposal to settle the Cyprus dispute. While the image of the Turk was long viewed as the nemesis of Europe, there was a change in mutual perceptions during the inter-war years thanks to the efforts of political leaders who were keen on initiating societal reforms and change their minds after listening to one another. The years of labor migration after 1960 had set the stage for mutual encounters and interwoven lives. This period diversified the stories of Europe in a dramatic way. The third critical moment involved the concomitant crises of Turkey and the EU after 2004 when Turkey’s membership in the EU finally seemed probable.