There is a growing recognition that conservation strategies should be designed accounting for cross-realm connections, such as freshwater connections to land and sea, to ensure effectiveness of marine spatial protection and minimize perverse outcomes of changing land-use. Yet, examples of integration across realms are relatively scarce, with most targeting priorities in a single realm, such as marine or freshwater, while minimizing threats originating in terrestrial ecosystems. To date, no study has optimized priorities across multiple realms to produce a spatially explicit integrated conservation plan that simultaneously accounts for multiple human activities at a national scale. This represents a major gap in the application of existing cross-realm planning theory. We present a national scale conservation framework for selecting protected areas using a case study of Papua New Guinea (PNG) that integrates multiple systems and ecological connectivity to account for cross-realm benefits and minimize threats of land-use and climate change. The relative importance of both the forests and inshore reef environments to PNG subsistence and commercial livelihoods emphasizes the importance of considering the connections between the land and sea. The plan was commissioned by the PNG Conservation and Environment Protection Authority and identifies a comprehensive set of priorities that meet conservation targets in both the land and sea. Our national-scale prioritization framework is useful for agencies and managers looking to implement actions given multiple objectives, including watershed management and biodiversity protection, and ensures actions are efficient and effective across the land and sea.