A phase-changeable memory device includes a substrate having a contact region on an upper surface thereof. An insulating interlayer on the substrate has an opening therein, and a lower electrode is formed in the opening. The lower electrode has a nitrided surface portion and is in electrical contact with the contact region of the substrate. A phase-changeable material layer pattern is on the lower electrode, and an upper electrode is on the phase-changeable material layer pattern. The insulating interlayer may have a nitrided surface portion and the phase-changeable material layer may be at least partially on the nitrided surface portion of the insulating interlayer. Methods of forming phase-changeable memory devices are also disclosed.