Institutions for environmental governance evolve differently across sectors. They also vary in the same sector when governments at two levels (national and subnational) have different political alignments. As the policy environment becomes more complex, with global problems like climate change, and politics more dividing, better coordination among various levels of government is a tough governance challenge. Scholars and practitioners need to realize how best to build institutions to bridge the various levels of government in different political environments and environmental sectors. This research analyzes the influence of intergovernmental relations in two environmental sectors in two localities with contrasting political alignments between two levels of government. It draws lessons from solid waste management and climate policy in two Malaysian states (Johor and Penang). In an evolving State and new policy arenas, when formal institutions for intergovernmental relations may not be effectively in place, politics play an even larger role through the discretionary power of federal and subnational authorities. An open political process can help with the engagement of different political groups and civil society to bring legitimacy, resources and efficiency to environmental management, if it is done with robust intergovernmental institutions; otherwise, intergovernmental relations can also become a tool for zero-sum games, cronyism and patrimonialism, which can undermine policies, and result in inefficiencies and ineffectiveness in environmental management.