Rivers support some of Earth's richest biodiversity1 and provide essential ecosystem services to society2, but they are often fragmented by barriers to free flow3. In Europe, attempts to quantify river connectivity have been hampered by the absence of a harmonized barrier database. Here we show that there are at least 1.2 million instream barriers in 36 European countries (with a mean density of 0.74 barriers per kilometre), 68 per cent of which are structures less than two metres in height that are often overlooked. Standardized walkover surveys along 2,715 kilometres of stream length for 147 rivers indicate that existing records underestimate barrier numbers by about 61 per cent. The highest barrier densities occur in the heavily modified rivers of central Europe and the lowest barrier densities occur in the most remote, sparsely populated alpine areas. Across Europe, the main predictors of barrier density are agricultural pressure, density of river-road crossings, extent of surface water and elevation. Relatively unfragmented rivers are still found in the Balkans, the Baltic states and parts of Scandinavia and southern Europe, but these require urgent protection from proposed dam developments. Our findings could inform the implementation of the EU Biodiversity Strategy, which aims to reconnect 25,000 kilometres of Europe's rivers by 2030, but achieving this will require a paradigm shift in river restoration that recognizes the widespread impacts caused by small barriers.