This paper presents an unsupervised approach for learning and classifying patterns that have spatio-temporal structure, using a spike-timing neural network with axonal conductance delays, from a very small set of training samples. Spatio-temporal patterns are converted into spike trains, which can be used to train the network with spike-timing dependent plasticity learning. A pattern is encoded as a string of “characters,” in which each character is a set of neurons that fired at a particular time step, as a result of the network being stimulated with the corresponding input. For classification we compute a similarity measure between a new sample and the training examples, based on the longest common subsequence dynamic programming algorithm to develop a fully unsupervised approach. The approach is tested on a dataset of hand-written digits, which include spatial and temporal information, with results comparable with other state-of-the-art supervised learning approaches.