A storage device includes a non-volatile memory including memory blocks, and a storage controller including a history buffer including plural history read level storage areas corresponding to the memory blocks. The storage controller dynamically adjusts a number of the history read level storage areas allocated to one or more of the plurality of memory blocks based on reliabilities of the memory blocks during runtime of the storage device. The storage controller increases a number of history read level storage areas allocated to a first memory block among the memory blocks that has a relatively low reliability with respect to the reliabilities of remaining ones of the memory blocks.