Trawl fishing constitutes an important part of the marine fisheries sector in Southeast Asia. It provides livelihoods and food for millions of people in coastal communities as well as feed for the region’s growing aquaculture sector. Trawl fisheries suffer from a multitude of problems, including overcapacity, excessive fishing effort, poor profitability and inadequate governance. The historical decline in catch per unit of effort, increasing proportion of low-value fish in trawl catches, widespread illegal fishing, and user conflicts reflect the weak management of these fisheries. Various measures implemented in the region have been insufficient to achieve sustainable outcomes. There has been little incentive for fishers to satisfactorily comply with the regulations. To understand better what kind of approaches would be effective and workable, the specific characteristics of SE Asian trawl fisheries are described and the fundamental barriers that must be addressed to improve sustainability and social benefits are identified. Meeting these challenges needs consideration of the socio-economic insecurity and the lack of alternative livelihoods as well as the complex ecological, cultural and institutional characteristics in the region. Simple, robust, equitable and easily enforced management measures are likely to work best in such a challenging environment. Properly implemented co-management systems would help to create incentives for individuals to cooperate. Trust building, participatory approaches, strong leadership and capacity building are important components to move SE Asian fisheries toward sustainability targets.