Until April 2012, all Spanish citizens were entitled to health care and policies had been developed at national and regional level to remove potential barriers of access, however, evidence suggested problems of access for immigrants. In order to identify factors affecting immigrants’ access to health care, we conducted a qualitative study based on individual interviews with healthcare managers (n = 27) and professionals (n = 65) in Catalonia and Andalusia, before the policy change that restricted access for some groups. A thematic analysis was carried out. Health professionals considered access to health care “easy” for immigrants and similar to access for autochthons in both regions. Clear barriers were identified to enter the health system (in obtaining the health card) and in using services, indicating a mismatch between the characteristics of services and those of immigrants. Results did not differ among regions, except for in Catalonia, where access to care was considered harder for users without a health card, due to the fees charged, and in general, because of the distance to primary health care in rural areas. In conclusion, despite the universal coverage granted by the Spanish healthcare system and developed health policies, a number of barriers in access emerged that would require implementing the existing policies. However, the measures taken in the context of the economic crisis are pointing in the opposite direction, towards maintaining or increasing barriers.