A memory device is provided. The memory device includes: a memory cell array including a plurality of rows; and a refresh control circuit including a plurality of registers each configured to store a row address. The refresh control circuit is configured to: determine, based on an incoming row address satisfying a replacement condition, in a first determination, whether to replace a first row address stored in a first register among the plurality of registers with the incoming row address based on a replacement probability; maintain the first row address stored in the first register or replace the first row address stored in the first register with the incoming row address based on a first result of the first determination; and determine, in a second determination, a victim row address to be refreshed based on a second row address stored in a second register among the plurality of registers.