Romania has a network of health mediators, meant to facilitate the communication between Roma communities and the medical staff. In this qualitative study, using data collected from three focus-groups with health mediators from Iaşi and Cluj counties, we provide significant information about the problematic issues related to the Roma population. The main challenges are the barriers affecting access to healthcare and the peculiarities of this ethnic group. Access to and healthcare provision would be improved with the development of the health professionals` cultural competences. Health mediators are the key elements in this process, all the more so as they are able to render innovative, collaborative care and program building with family physicians and hospitals, committed to the comprehensive and preventive treatment of the Roma population.