Transboundary marine socio-ecological systems (SESs) are complex and dynamic systems. Enhancing the sustainability of such systems requires adaptive governance supported by polycentric structures. However, adaptive governance of marine SESs across national boundaries can be challenging, as significant differences in institutional arrangements for resource management and adaptive governance capabilities may exist. The limitations of various institutional arrangements and the challenges of adaptive governance across borders are still poorly understood. We offer a comparative study of two marine co-management systems, in southern Kenya and northern Tanzania, which are bound by different legislative environments to elucidate how institutions might limit or enable adaptive governance at the local and transboundary scale. The legislative environment is characterized based on a review of the literature. The structural properties of the co-management systems are examined for evidence of polycentricity using social network analysis. Across the different co-management contexts, we discover similar and distinct institutional opportunities and challenges for adaptive governance. Both co-management regimes foster the participation of diverse actors and multiple interactions. However, both show strong sectoral tendencies and high centrality of government, which can hinder adaptive governance. There are more autonomous decision units in Tanzania’s co-management network, hence a more robust social context for polycentricism compared to Kenya. A shift towards enhanced polycentricity to foster adaptive governance of the Kenya-Tanzania transboundary marine SES will require policy frameworks that enhance cross-sectoral integration and create opportunities for multi-stakeholder bridging.