A novel online learning algorithm for Spiking Neural Networks (SNNs) with dynamically adaptive structure is presented. The main contribution of this work lies in the fact that the proposed adaptive SNN is able to classify spike-based spatio-temporal inputs after just one presentation of the training set, i.e. in one pass only, and does not require the entire training set to be available at once. Both the structure and weights of the SNN are learned dynamically through a combination of unsupervised and supervised learning paradigms. The proposed feed-forward SNN consists of three layers of spiking neurons: an input layer which temporally encodes real valued features into spike-based spatio-temporal patterns, a hidden layer of dynamically grown and pruned neurons which perform spatio-temporal clustering, and an output layer for classification. An unsupervised spiking-based clustering algorithm is implemented by the hidden layer whose spiking neurons are trained to compute a temporal Radial Basis Function (RBF) where incoming inputs will selectively activate hidden neurons based on how close the inputs are to the preferred inputs of the hidden neurons. The centre of each hidden RBF spiking neuron is represented by its time to first spike. In addition, a growing and pruning strategy is proposed to adjust the structure of the hidden layer ‘on-the-fly’ as inputs are presented to the SNN. Both the weights and the centres of the hidden RBF neurons are learned in an unsupervised way and classification at the output layer is achieved through supervised learning where the learning windows proposed for STDP and anti-STDP are used to adjust the weights of the output neurons afferent connections. Competition at both the hidden and the output layers is achieved through the use of lateral inhibitory connections between the neurons of each layer. The proposed online learning algorithm is validated on several benchmark datasets. The evaluation results demonstrate that SNNs trained with the proposed approach require only one pass through the training set in order to classify the inputs with comparable accuracies to existing SNN-based approaches as well as traditional representative classifiers.