A storage device includes a controller that implements an interlaced magnetic recording scheme with prioritized random access. According to one implementation, a controller is configured to write data at a first linear density to alternating data tracks and write data at a second linear density to one or more data tracks interlaced with the alternating data tracks.