Carbon storage is an important component of ecosystem services. Under climate warming and human activities, land use/land cover (LULC) have been undergoing tremendous change, leading to spatio-temporal variations in carbon storage. Based on seven series of LULC data and combined with carbon module of Integrated Valuation of Ecosystem Services and Tradeoffs (InVEST) model, spatial-temporal changes in LULC types and carbon storage were analyzed and estimated for Heilongjiang Province, Northeast China. Results show varied carbon storage among different types of LULC. Forest and cropland are the dominant LULC types in Heilongjiang Province, Northeast China, accounting for 46–49% (20.90 × 104–22.12 × 104km2) and 30–37% (13.56 × 104–16.70 × 104km2) of the total area. Areal extents of forest, grassland, and unused land declined from 1980 to 2015, by 1.22, 0.84, and 1.11 × 104km2, respectively; while those of cropland and construction land expanded, by 3.14 and 0.08 × 104km2, respectively. From 1980 to 2015, carbon storage displayed consistent change trends with those of LULC types: carbon storage of forest, grassland, and unused land decreased by 236.22, 116.61 and 21.82 × 106 Mg C, respectively; and those of cropland and construction land increased by 414.65 and 0.99 × 106 Mg C, respectively. The total carbon storage in the study region was 6,863.06 × 106–6,907.64 × 106 Mg C, for which the forest, cropland, and grassland were the major contributor (6,778.75 × 106–6,840.57 × 106 Mg C). Due to the conversion of large extents of forest, grassland, and unused land to cropland, which facilitated the formation of carbon sinks and thus enlarged the carbon storage by 45.36 × 106 Mg C from 1980 to 2015. Frequent forest fires, urban expansion, farmland reclamation, and engineering construction were the important factors of changes in the LULC, accelerating permafrost degradation and leading to obvious changes in the total carbon storage in the Heilongjiang Province, Northeast China. Therefore, the estimation of carbon storage in different LULC types can provide important data support and have important implications for evaluation of ecosystem services and carbon cycle.