The existence of excessive fishing capacity is globally recognized by resource managers as a major problem for fisheries, and it is responsible for the degradation of fishery resources and for significant economic waste. Estimates of fishing capacity and capacity utilization may provide helpful tools in designing an effective capacity management plan for Mediterranean fisheries. In this study, the fishing capacity and capacity utilization of eastern Mediterranean purse seiners were assessed using data envelopment analysis (DEA). Estimates were made for individual vessels based on the level of inputs used and outputs produced, relative to other vessels operating under similar conditions. Results indicated similar excess capacity for target species, which is in accordance with how the fishery operated. The 24–40-m fleet segment was found to be more efficient than the 12–24-m fleet segment in terms of landing weights. It was evidenced that purse seiners could have increased their catch during 2000–2005 by approximately 23% by increasing the variable inputs, for example days fished. Conversely, a fleet of smaller size could have achieved the reported catch. Under the condition that the remaining vessels will be fully utilized, a proportional decrease in the fleet size might seem a rational management measure towards reducing overexploitation and attaining sustainable fisheries in the eastern Mediterranean Sea.