Thermal energy storage (TES) systems are used with heating, ventilation, and air conditioning (HVAC) systems in buildings to reduce the electricity cost for HVAC where time-of-use rates are in place. Latent heat storage, primarily using ice as a phase-change material (PCM), is the most commonly-used form of TES in buildings due to its high energy density. However, latent heat storage is fixed-temperature; the storage system must be charged and discharged at the phase-change temperature (PCT) of the PCM. A variable-temperature TES system would have the advantage of allowing the system to be charged and discharged at the operating temperatures that would minimize the required power input. Furthermore, if the temperature could be varied sufficiently, the same PCM could be used for both heat storage and cold storage (which is not possible for fixed-temperature systems). High energy-density variable-temperature storage could potentially be achieved using thermochemical energy storage. In addition, finding ways to tune the PCT of a PCM has been an active area of research in recent years. In this paper, we examine how to obtain the most cost savings from a variable-temperature TES system by optimizing the PCT of the PCM in both heating and cooling modes. A model of a building HVAC system is developed, which includes a heat pump, secondary loop, auxiliary electric heating, and a variable-temperature TES tank. An algorithm determines the operating temperatures of this system in terms of the PCT of the PCM. An optimization algorithm is used to determine the values of the PCT that will minimize operating costs. It is shown that varying the PCT during operation results in cost savings for both cooling and heating modes, and that the majority of these cost savings can be obtained by using only two different values of the PCT each day.