Disclosed is a phase-changeable memory device and method of programming the same. The phase-changeable memory device includes memory cells each having multiple states, and a program pulse generator providing current pulses to the memory cells. The program pulse generator initializes a memory cell to a reset or set state by applying a first pulse thereto and thereafter provides a second pulse to program the memory cell to one of the multiple states. According to the invention, as a memory cell is programmed after being initialized to a reset or set state, it is possible to correctly program the memory cell without influence from the previous state of the memory cell.