The residential building stock holds a large energy efficiency improvement potential related to energy upgrading of the building envelope. Details about the heterogeneity of the building stock are paramount to perform a proper assessment of attractive energy efficiency improvements for end-users. Based on a sample of buildings, the study develops methods to identify potentials for heterogeneous building-tailored energy efficiency improvements, to reduce heat consumption, and evaluates their cost-effectiveness in the framework of a district heating area in Denmark. The study accounts for rebound effects and develops both technical (gross) and more realistic (net) potentials, allowing a more accurate analysis of attractive energy efficiency improvements. The analysis is novel as the underlying model relies on building characteristics rather than synthetic archetypes, which can lead to loss of diversity (e.g. in variation of costs and potentials) and thereby discarding cost-effective potentials. The analysis also investigates the sensitivity of the results to assumptions about the discount rate and focuses on the effect of exposing the end-user to different district heating tariffs and the consequent total cost-effective investments. The outcomes show that cost-effective energy efficiency improvements vary considerably, in size and type, among the heterogeneous building stock considered. In regard to district heating tariffs, when all the cost components are variable, the total cost-effective potential increases considerably, with specific energy efficiency improvements distributed differently among building categories, and with the cost components providing different incentives to invest. Heterogeneity, and different tariff policies, thus does matter, when evaluating economically attractive investments in energy efficiency improvements for buildings.