Background: Health literacy concerns the capacities of people to meet the complex demands of health in modern society. In spite of the growing attention for the concept among European health policymakers, researchers and practitioners, information about the status of health literacy in Europe remains scarce. This article presents selected findings from the first European comparative survey on health literacy in populations. Methods: The European health literacy survey (HLS-EU) was conducted in eight countries: Austria, Bulgaria, Germany, Greece, Ireland, the Netherlands, Poland and Spain (n = 1000 per country, n = 8000 total sample). Data collection was based on Eurobarometer standards and the implementation of the HLS-EU-Q (questionnaire) in computer-assisted or paper-assisted personal interviews. Results: The HLS-EU-Q constructed four levels of health literacy: insufficient, problematic, sufficient and excellent. At least 1 in 10 (12%) respondents showed insufficient health literacy and almost 1 in 2 (47%) had limited (insufficient or problematic) health literacy. However, the distribution of levels differed substantially across countries (29–62%). Subgroups within the population, defined by financial deprivation, low social status, low education or old age, had higher proportions of people with limited health literacy, suggesting the presence of a social gradient which was also confirmed by raw bivariate correlations and a multivariate linear regression model. Discussion: Limited health literacy represents an important challenge for health policies and practices across Europe, but to a different degree for different countries. The social gradient in health literacy must be taken into account when developing public health strategies to improve health equity in Europe.