This paper explores the evolution of productivity of the traditional fishery fleet resources that operates in the Arabian Gulf. This fleet produced 65% of traditional total fishery production in 2006. The gap between total consumption (231,000 tons) and local fish production (81,000 tons) in 2006 pushed towards increasing fishing effort numbers, and resulted in over-fishing. Estimation of total factor productivity changes by evaluating both efficiency and technical changes became a necessary step for a sustainable traditional fishery. This study used Malmquist Productivity Index estimation (MPI) over the period 2001-2006, on both yearly and monthly bases. Results showed that the average yearly MPI ranged from -5.4% to +54.7%, which require improving the technology used by small fishing boats applying Trap fishing methods. Large fishing boats using Trap at South of the Gulf need to improve its technology to avoid the negative impact (-5.5%) on MPI. Fishermen skills need to be improved to increase their efficiency, especially for those using small boats and Manasb fishing methods. Both, pure-efficiency changes and scale-efficiency changes, are tools to direct programs of increasing efficiency of fishermen. Based on yearly and monthly total factor productivity changes and its components, this study will help policy makers in setting priorities regarding fishing technology and fishermen skills using small and large boats at different fishing grounds.