Streams across the world are highly fragmented due to the presence of in-stream barriers (e.g., dams and stream-road crossings), many of which restrict or block fish passage. Retrofitting or replacing these structures is a high priority for restoring habitat connectivity for native fishes and other aquatic organisms in the Pacific Northwest. The task of restoring habitat connectivity for problematic stream-road crossings is daunting given the many thousands of barriers that are present and the massive financial investments required. Further, the potential risks to road infrastructure from flooding, debris flows, and climate change will need to be addressed to ensure the best allocation of resources. In this study, I developed and implemented an approach to prioritize culvert replacements by including considerations of fish access, culvert replacement costs, and potential climate change impacts on the risk of culvert failure. The approach described herein involves consideration of expected costs throughout the life-cycle of culverts and an optimization model to select culvert replacements in the context of multiple objectives. I illustrate the application and explore trade-offs in the Siuslaw National Forest, Oregon, a forest with hundreds of stream-road crossings where culvert replacements are being actively carried out. A variety of native fishes are considered, including salmon, trout, sculpin, dace, and lamprey. Within this setting, I applied the road crossing life-cycle and optimization models to prioritize replacements of culverts across a broad landscape and to explore how contrasting management objectives can change our decisions and on-the-ground actions. I found that the selection of culverts for replacement was variable, depending on the replacement costs used, site-specific risk, upstream habitat goals, and species in question. The framework presented here can help to determine which culverts to replace in order to improve connectivity for stream fishes. Evaluating climate change impacts did not change culvert replacement or size selections, but this could be different in areas predicted to have greater climate change impacts.