Background In order to provide effective primary care for refugees and to develop interventions tailored to them, we must know their needs. Little is known of the health needs and experiences of recently arrived refugees and other migrants throughout their journey through Europe. We aimed to gain insight into their health needs, barriers in access and wishes regarding primary health care. Methods In the spring of 2016, we conducted a qualitative, comparative case study in seven EU countries in a centre of first arrival, two transit centres, two intermediate-stay centres and two longer-stay centres using a Participatory Learning and Action research methodology. A total of 98 refugees and 25 healthcare workers participated in 43 sessions. Transcripts and sessions reports were coded and thematically analyzed by local researchers using the same format at all sites; data were synthesized and further analyzed by two other researchers independently. Results The main health problems of the participants related to war and to their harsh journey like common infections and psychological distress. They encountered important barriers in accessing healthcare: time pressure, linguistic and cultural differences and lack of continuity of care. They wish for compassionate, culturally sensitive healthcare workers and for more information on procedures and health promotion. Conclusion Health of refugees on the move in Europe is jeopardized by their bad living circumstances and barriers in access to healthcare. To address their needs, healthcare workers have to be trained in providing integrated, compassionate and cultural competent healthcare.