The development of X-ray and electron diffraction methods with ultrahigh time resolution has made it possible to map directly, at the atomic level, structural changes in solids induced by laser excitation (1,2,3,4,5,6,7,8). This has resulted in unprecedented insights into the lattice dynamics of solids undergoing phase transitions. In aluminium, for example, femtosecond optical excitation hardly affects the potential energy surface of the lattice; instead, melting of the material is governed by the transfer of thermal energy between the excited electrons and the initially cold lattice (1). In semiconductors, in contrast, exciting ∼10 per cent of the valence electrons results in non-thermal lattice collapse owing to the antibonding character of the conduction band (2,3,4,5,9,10). These different material responses raise the intriguing question of how Peierls-distorted systems (11) such as bismuth (12) will respond to strong excitations. The evolution of the atomic configuration of bismuth upon excitation of its A1g lattice mode, which involves damped oscillations of atoms along the direction of the Peierls distortion of the crystal, has been probed (6,7,8), but the actual melting of the material has not yet been investigated. Here we present a femtosecond electron diffraction study of the structural changes in crystalline bismuth as it undergoes laser-induced melting. We find that the dynamics of the phase transition depend strongly on the excitation intensity, with melting occurring within 190 fs (that is, within half a period of the unperturbed A1g lattice mode (6,7,8)) at the highest excitation. We attribute the surprising speed of the melting process to laser-induced changes in the potential energy surface of the lattice, which result in strong acceleration of the atoms along the longitudinal direction of the lattice and efficient coupling of this motion to an unstable transverse vibrational mode. That is, the atomic motions in crystalline bismuth can be electronically accelerated so that the solid-to-liquid (13) phase transition occurs on a sub-vibrational timescale.