In this article, we consider the role of ocean literacy in coastal communities as an approach that fosters relevant, community-based learning. We also propose solutions to challenges facing human-ocean relationships by cultivating common understanding and collective action. We present four examples of community-based ocean literacy in Mi'kma'ki/Atlantic Canada demonstrate how intersectional approaches to ocean literacy that are context-specific and responsive to community priorities can foster healthier human-ocean relationships: (1) Oceans Week Halifax's organization of community events to strengthen human-ocean relationships; (2) the Apoqnmatulti'k (Mi'kmaw: we help each other) project's partnerships between Mi'kmaq and local knowledge holders and academia; (3) Fishing For Success's (Newfoundland and Labrador) inclusive approaches to connecting marginalized communities to the ocean; and (4) the Co-Existing With North Atlantic Right Whale Project's protection of whales without jeopardizing coastal community livelihoods. Without denying there are barriers to bridging community learning with formal education, we focus on opportunities for collaborations and the importance of ocean optimism in guiding these urgently needed efforts to benefit future community-based, ocean-focused, and solutions-orientated initiatives.