Given the need for decarbonization of the heating sector and the acute need of a propane replacement in the U.S. Upper Midwest, this study quantifies the techno-economic characteristics of sustainable heating electrification in isolated rural, residential buildings in cold climates without natural gas supply. Archetypal buildings are modeled under four levels of electrification. At each electrification level, a parametric solar photovoltaic (PV) sizing analysis is performed and the total life cycle cost, renewable fraction and greenhouse gas (GHG) emissions are calculated based on the primary energy supply for each building type. Cost optimal solutions are stress-tested with multi-dimensional sensitivity analyses. The results show that the total life cycle cost favors heating electrification in all cases and combining PV with heat pumps can reduce residential building GHG emissions by up to 50% immediately. This effect will grow over time, with over 90% reduction of building emissions if renewable energy targets are met. In using primary energy and emissions along with the multi-dimensional sensitivities, this study unique demonstrates the complex techno-economic interactions of PV and heat pumps. It is concluded that electrification is an economically viable decarbonization method for cold climates both now and in the future.