The idea of an online visual vocabulary is proposed. In contrast to the accepted strategy of generating vocabularies offline, using the k-means clustering over all the features extracted form all the images in a dataset, an online vocabulary is dynamic and evolves iteratively over time as new observations are made.  Hence, it is much more suitable for online robotic applications, such as exploration, landmark detection, and SLAM, where the future is unknown. We present two different strategies for building online vocabularies. The first strategy produces a vocabulary, which optimizes the k-centres objective of minimizing the maximum distance of a a feature from the closest vocabulary word. The second strategy produces a vocabulary by randomly sampling from the current vocabulary and the features in the current observation. We show that both the algorithms are able to produce distance matrices which have positive rank correlation with distance matrices computed using an offline k-means vocabulary. We discover that the online random vocabulary is consistently effective at approximating the behaviour of the offline k-means vocabulary, at least for the moderate sized datasets we examine.