Methods and apparatus are provided for overwriting data in a probe-based data storage device in which data bits are represented by the presence and absence of pits at bit positions on a storage surface, the pits being formed in the storage surface by a probe mechanism of the device. Input data is coded to generate a coded bit sequence and an overwrite technique is employed to record the coded bit sequence on the storage surface over an old, previously-recorded bit sequence. Together with the properties of the coded bit sequence, the overwrite technique exploits the physical mechanism of the write process in that, with appropriate spacing of the bit positions on the storage surface, writing a pit at a bit position can erase an existing pit within a defined number of neighboring bit positions. In addition, the overwrite technique involves reading at least certain bits of the old bit sequence, whereby the pattern of data written on the storage surface in an overwrite operation is determined in part by the results of reading old data.