Plasmas have long been regarded as the most disordered state of matter; nevertheless, a set of colloidal particles introduced into a charge-neutral plasma can spontaneously exhibit ordered crystalline structures(1,2)--so-called ’plasma crystals’. Such systems, which reach equilibrium very rapidly and can be easily tuned between their ordered and disordered states, are ideally suited for investigating the processes underlying the solid-to-liquid phase transition. Here we report the results of experiments on ’flat’ plasma crystals (with thicknesses of only a few lattice planes) which suggest that the melting transition occurs through two fundamental intermediate stages. On melting, the crystal first enters a state characterized by islands of crystalline order about which streams of particles flow. The crystalline regions then dissolve as the vibrational energy of the system increases, but this is accompanied by a temporary increase in orientational order before the system finally enters a disordered, liquid state. The unexpected ’vibrational’ phase, characterized by enhanced orientational order, might arise as a consequence of the mixed two- and three-dimensional nature of the flat plasma crystals. Alternatively, it may indicate the existence of a new intermediate state in melting transitions more generally.