Provided are a phase-change memory device and a method of fabricating the same. The device may include memory cells provided at intersections of word lines and bit lines that extend along first and second directions crossing each other, and a mold layer including thermal insulating regions, such as air gaps, that may be provided between the memory cells to separate the memory cells from each other. Each of the memory cells may include a lower electrode electrically connected to the word line to have a first width in the first direction, an upper electrode electrically connected to the bit line to have a second width greater than the first width in the first direction, and a phase-change layer provided between the lower and upper electrodes to have the first width in the first direction.