Exploration for belowground oil and gas deposits in boreal forests of western Canada involves the creation of seismic lines, which are linear disturbances where seismic equipment operates. Seismic lines cause habitat fragmentation and increase predator access to intact forest, leading to declines of some wildlife populations, particularly the woodland caribou, Rangifer tarandus caribou. Restoration of forests within seismic lines is an important activity to reduce habitat fragmentation. We present an optimization model with the objective of determining landscape restoration strategies that maximize the area of connected habitat for a caribou population in a fragmented landscape. We used our model to find optimal strategies for seismic line restoration in the Cold Lake Area of Alberta, Canada, a 6726-km2 expanse of boreal forest that represents prime caribou habitat. We formulate mixed integer programming models that depict the landscape as a network of interconnected habitat patches. We develop and compare formulations that emphasize the population’s local or long-distance access to habitat. Optimal restoration involves a mix of two strategies: the first establishes short-distance connections between forest patches with large areas of intact habitat and the second establishes corridors between areas with known species locations and large amounts of suitable habitat. Our approach reveals the trade-offs between these strategies and finds the optimal restoration solutions under a limited budget. The approach is generalizable and applicable to other species sensitive to changes in landscape-level connectivity.