A data storage device is disclosed comprising a first head actuated radially over a first disk surface, and a second head actuated radially over a second disk surface. A seek operation seeks the first head to a first fly height calibration track and seeks the second head to a second fly height calibration track. During a revolution of the first and second disk surfaces the first head is used to read the first fly height calibration track in order to calibrate a first fly height actuator for the first head, and after switching from the first head to the second head, the second head is used to read the second fly height calibration track in order to calibrate a second fly height actuator for the second head.