World food production has increased substantially in the past century, thanks mostly to the increase in the use of oil as input in the production processes. This growing use of fossil fuels has negative effects, both on the environment and the production costs. Fishing is a fuel consuming food production activity, and its energy efficiency performance has worsened over time. World-wide fisheries are also suffering from overexploitation, which contributes to the poor efficiency performance, adding more pressure and criticism on this economic activity. In this paper we analyzed the energy efficiency performance of more than 20,000 European Union (EU) fishing vessels for the period 2002-2008, using the edible energy return on investment (EROI) indicator. The vessels analyzed, grouped in 49 different fleets, represented 25% of the vessels and 33% of the landings of the EU fishing sector. These EU fishing fleets' average EROI for 2008 was 0.11, which translates to an energy content of the fuel burned that is 9 times greater than the edible energy content of the catch. Hence, the significance of this study arises from the use of time-series data on a relevant part of the EU fleet that showed stable or even slight improvements on the EROI over time. Moreover, results showed that the energy efficiency of the different fleets varied significantly (from 0.02 to 1.12), mainly depending on the fishing gear and the vessel length. The performance of the most efficient fleets, such as large pelagic trawlers and seiners, was comparable to many agricultural production activities. The plausible drivers behind these trends are further considered.