Gilsonite, as a type of natural asphalt binder, has been used to improve the high-temperature performance of regular asphalt binders. However, the addition of Gilsonite may compromise binders' low-temperature thermal cracking resistance. In this research, polyethylene glycol (PEG), as one type of the phase change materials (PCMs), was used as an innovative material to balance the impacts of Gilsonite on high and low performance of asphalt binders. The dosages of Gilsonite and PEG were first determined based on the materials' rheological behaviors at low temperatures. The performance of the PEG-Gilsonite-modified binder was then fully evaluated in terms of the resistance to cracking and rutting at various temperatures. Thermal tests were also conducted to assess the thermal behaviors of the modified binders. The testing results indicate that with the proper dosage of Gilsonite and PEG, the rutting resistance of the binder can be improved without sacrificing its low-temperature performance. With the addition of the PCM, the binder was tested to have high volumetric heat capacity, which indicates PCM can reduce the rate and the magnitude of the temperature changes in pavements.