In an attempt to address the negative ecological impacts of habitat fragmentation, wildlife corridors have been proposed as a way to connect areas of biological significance. In this article we introduce a model to maximize the amount of suitable habitat in a fully connected parcel network linking core habitat areas, subject to a constraint on the funds available for land acquisition. The economic framework of maximizing benefits subject to a budget constraint that we employ is a divergence from other recently proposed models that focus only on minimizing the cost of a single parcel-wide corridor. While the budget constrained optimization model that we introduce is intuitively appealing, it presents substantial computational challenges above and beyond determining the cost-minimizing corridor. We formulate the wildlife corridor design problem formally as the so-called connection subgraph problem. This graph problem, NP-hard in terms of the worst case computational complexity, demonstrates an easy-hard-easy pattern in solution runtime. We present a solution method for this optimization problem using a network flow based Mixed Integer Programming (MIP) formulation, and introduce a hybrid technique to improve scalability. We apply our model and methods to real data collected for the optimal design of a wildlife corridor for grizzly bears in the U.S. Northern Rockies, illustrating the underlying computational complexities by varying the granularity of the parcels available for acquisition. In addition, we show that budget constrained optimization drastically increases total habitat suitability of the corridor over parcel selection based solely on cost minimization. The model and solution method developed here are general and can be applied, in addition, to conservation of other species or even to problems arising in other fields such as social networks.