This study explores the technical and scale efficiency of two types of Greek fishing vessels, small-scale vessels and bottom trawlers, using a bias-corrected input-oriented Data Envelopment Analysis model. Moreover, the associations between efficiency scores and vessel’s and skipper’s characteristics are also explored. The results indicate that small-scale vessels achieve a very low average technical efficiency score (0.42) but a much higher scale efficiency score (0.81). Conversely, bottom trawlers achieve lower scale but higher technical efficiency scores (0.68 and 0.73, respectively). One important finding of this study is that the technical efficiency of small-scale vessels, in contrast to trawlers, is positively associated with the experience of the skipper. In a looser context, it can be said that small-scale fisheries mainly rely on skill, whereas bottom trawlers rely more on technology. This study concludes that there is space for improvement in efficiency, mainly for small-scale vessels, which could allow the achievement of the same level of output by using reduced inputs.