This work examines the cross-border cooperation among the Nordic countries and with Russia by analysing the Interreg IIIA North and Interreg IIIA Öresund programmes. The focus is centered on the conditions that the well functioning cross-border cooperation necessitates, and challenges and barriers that it faces. Also, the actions to tackle the challenges, as well as the utilization of earlier experiences, are examined and analysed by using interviews and survey as research methods. This work shows that the differences in legislation and in administrative systems, together with finance and attitudes, are the major barriers for the cooperation. Accordingly, well working cross-border cooperation requires tolerance towards the differences, genuine view on cooperation, as well as shared understanding of the need and purpose of the cooperation. In addition, the careful strategy and project planning is of vital importance. It is argued that some of the barriers can be alleviated and overcome on project and programme levels, whereas other barriers can only be solved on national and transnational levels. However, the barriers and need for actions vary a great deal depending on the partners, projects, and larger circumstances. Finally, it is suggested that by continuing the long-term cooperation and by utilizing the earlier experiences, some of the barriers and biased attitudes can be overcome.