We consider the problem of using a stochastic approximation algorithm to perform online tracking in a non-stationary environment characterised by abrupt "regime changes". The primary contribution of this paper is a new approach for adaptive stepsize selection that is suitable for this type of non-stationarity. Our approach is pre-emptive rather than reactive, and is based on a strategy of maximising the rate of adaptation, subject to a constraint on the probability that the iterates fall outside a pre-determined range of acceptable error. The basis for our approach is provided by the theory of weak convergence for stochastic approximation algorithms. Crown Copyright (C) 2007 Published by Elsevier Ltd. All rights reserved.