Methods are provided for fabricating contacts in integrated circuit devices, such as phase-change memories. A protection layer and a sacrificial layer are sequentially formed on a semiconductor substrate. A contact hole is formed through the sacrificial layer and the protection layer. A conductive layer is formed on the sacrificial layer and in the contact hole, and portions of the conductive layer and the sacrificial layer are removed to expose the protection layer and form a conductive plug protruding from the protection layer. A protruding portion of the conductive plug removed to leave a contact plug in the protection layer. A phase-change data storage element may be formed on the contact plug.