Sequence memories play an important role in biological systems. This work demonstrates how a sequence memory may be built from biologically plausible spiking neural components. The memory is incorporated in a sequence machine, an automaton that can perform on-line learning and prediction of sequences of symbols. The sequence machine comprises an associative memory which is a variant of Pentti Kanerva"s Sparse Distributed Memory, together with a separate memory for storing the sequence context or history. The symbols constituting a sequence are encoded as rank-ordered N-of-M codes, each code being implemented as a burst of spikes emitted by a layer of neurons. When appropriate neural structures are used the spike bursts maintain coherence and stability as they pass through successive neural layers. The system is modelled using a representation of order that abstracts time, and the abstracted system is shown to perform equivalently to a low-level spiking neural system. The spiking neural implementation of the sequence memory model highlights issues that arise when engineering high-level systems with asynchronous spiking neurons as building blocks.