The ultra-high demand for faster computers is currently tackled by traditional methods such as size-scaling (for increasing the number of devices), but this is rapidly becoming almost impossible, due to physical and lithographic limitations. To boost the speed of computers without increasing the number of logic devices, the only feasible solution is to increase the number of operations performed by a device, which is impossible to achieve using current silicon-based logic devices. Multiple operations in phase-change-based logic devices have been achieved using crystallization; however, they can achieve only the best (or fastest) speeds of several 10’s of nanoseconds. A difficulty also arises from the trade-off between the speed of crystallization and long-term stability of the amorphous phase. We overcome here the contradictory nature between the crystallization speed and long-term stability by instead controlling the process of melting through pre-melting disordering effects, while maintaining the superior advantage of phase-change-based logic devices over silicon-based logic devices. Multiple and low power Boolean algebraic operations, NOR and NAND, were achieved with a melting speed of just 900 picoseconds. Ab initio molecular-dynamics simulations and in situ electrical characterization revealed the origin (i.e. bond-buckling of atoms) and kinetics (e.g. discontinuous-like behavior) of melting through pre-melting disordering, which were key to increasing the melting speeds. By a subtle investigation of the well-characterized phase-transition behavior, this simple method provides an elegant solution to boost significantly the speed of phase-change-based logic devices, thus paving the way for achieving computers that can perform computations towards terahertz processing rates.