The small-scale fishermen of Colombia face a wide range of problems and conflicts. While many problems are shared among individuals from both the Atlantic and the Pacific coasts (bi-coastal), others are unique to a subset of the communities, only occur on one of the coasts (uni-coastal) or in an individual locality. To come to grips with the major problems for these fisheries requires establishing a fisheries management strategy that can prioritize solutions at different levels: national, coastal, and local. This study describes the solutions identified by three sets of stakeholders: fishermen, local leaders and fisheries experts, to improve small-scale fisheries management in Colombia. Some cross-cutting solutions were recommended by all three sets of stakeholders. In other cases, only two of the three stakeholder groups agreed on certain proposals, and some isolated solutions were found in only one type of stakeholder. All three sets of stakeholders recommended that the government put in place fundamental regulatory framework for small-scale fisheries including support for alternative employment opportunities to reduce fishing pressure on the resources. Some but not all groups supported specific measures, such as gear restrictions, closed areas and closed seasons. There was also a clear need to distinguish those truly engaged in fishing as their livelihood from opportunists moving in and out of the sector. Specific recommendations are here presented to reform and restructure governance through co-management, and to develop a consensus among the main government and user stakeholders.