This paper reviews some key governance challenges that are experienced in the implementation of fisheries co-management programmes. Specific lessons are drawn from Malawi and, to some extent, from other southern African experiences. Governments and representative user committees are supposedly key partners in the co-management programmes. Many studies of CPR governance start from a user-group perspective and examine how resource users operate in a multitiered, embedded constellation of institutional arrangements. However, while recognizing the validity of these approaches, this paper examines more closely the role of governments in crafting co-management arrangements and creating facilitating environments for stakeholder participation. Given that the government is the dominating factor in many fishery governance arrangements, it is important to gain understanding about the specifics of its role in these processes. Many fisheries co-management arrangements in southern Africa are, however, generally consultative, and partnerships tend to be unequal. Nevertheless, there are some co-management sites where co-operative and advisory types of co-management exist. This paper asserts that effective co-management demands the creation of an enabling environment that gives power and authority to both government and resource users at community and district levels in a broader participatory management process. Strategies proposed in relation to participation and accountability include shifts from instructive to consultative forms of co-management, scaling up co-management processes and inclusiveness through decentralisation reforms, community empowerment through revenue sharing and the provision of an enabling environment for a greater level of participation by communities in decision-making processes, and the formulation of clear objectives and roles of actors at both the community and the district assembly levels. By-laws at the district authority level should be legally binding and according to which fisheries resources are considered as natural goods for the benefit of the local communities. Taxation schemes for appropriation of the resources are important for the sustainable management of fisheries resources, especially in establishing measures for the regulation of fishery related activities. Roles of specific stakeholders should be clear as their support may be crucial to the success or failure of co-management initiatives. Incentives for community participation should primarily aim at resource recovery and sustainable utilisation of the fisheries resources for improved community livelihoods and not on monetary rewards. Where fish resources are overexploited, co-management programmes should include alternative sources of income.