A technique for sanitizing data storage devices, such as magnetic disks, is disclosed. Logical data storage units such as files or portions thereof may be individually deleted and sanitized on a disk. A disk is divided into physical disk regions, each comprising one or more blocks. The contents of the disk are encrypted using a separate encryption key for each physical disk region. If a file or other data structure located in a first disk region and encrypted using a first encryption key is to be deleted, the logical portions (i.e., blocks) of that region that do not belong to the file are re-encrypted using a second encryption key, and the first encryption key is deleted.