The environmental benefits and costs of conservation policies often vary over space and through time. Accounting for this spatial and temporal heterogeneity has important implications for the potential cost effectiveness of different payment program designs. In this study, we examine the cost efficiency gain from spatial and temporal targeting in payment designs for forest carbon storage in the Central and Southern Appalachian Mountains in the Eastern United States. We run a forest land change model and a carbon simulation model utilizing a panel data on forest land and its competing uses, economic returns, and spatial characteristics for each 1 km grid cells in 1992, 2001, 2006 and 2011. A time- and space-specific carbon cost for each individual 1 km grid cell is calculated that captures the spatial and temporal heterogeneity in carbon cost efficiency. From there, we compare carbon cost efficiency levels of various payment designs that allow for different degrees of spatial and temporal flexibility. We find that 1) spatial targeting improves carbon cost efficiency, and this efficiency gain is larger as payments become more narrowly targeted, 2) this carbon efficiency gain is present in all market conditions, but is largest in a moderately growing market and smallest in a downturn market, 3) accounting for temporal heterogeneity results in even larger carbon efficiency gains, almost double those from spatial targeting. Just as policies that enable spatial targeting (e.g., auctions) increase cost efficiency savings, so too will policy mechanisms that emphasize budget flexibility through time. These could include utilizing loans or flexible conservation financing, or allowing movement across budgeting categories within a given time period.