An optical disk apparatus which can record data by means of transition between an amorphous state and a crystalline state and enables overwriting of data. Test data are recorded into a test area of an optical disk by radiating a laser beam of recording power. The recorded test data are erased by radiating a laser beam of erasing power to the test area of the optical disk while a rotational speed of the optical disk is varied. An erasure performance for erasing the test data is computed at each rotational speed, and the erasure performance is compared with the predetermined threshold value. The higher the rotational speed, the lower the erasure performance. From among the rotational speeds at which superior erasure performance is achieved, the maximum rotational speed is selected. Data are written over the data area of the optical disk at the thus-selected maximum rotational speed.