A phase change memory device may include an integrated circuit substrate and first and second phase change memory elements on the integrated circuit substrate. The first phase change memory element may include a first phase change material having a first crystallization temperature. The second phase change memory element may include a second phase change material having a second crystallization temperature. Moreover, the first and second crystallization temperatures may be different so that the first and second phase change memory elements are programmable at different temperatures. Related methods and systems are also discussed.