This paper proposes an incremental extremely random forest (IERF) algorithm, dealing with online learning classification with streaming data, especially with small streaming data. In this method, newly arrived examples are stored at the leaf nodes and used to determine when to split the leaf nodes combined with Gini index, so the trees can be expanded efficiently and fast with a few examples. The proposed online IERF algorithm gives more competitive or even better performance, than the offline extremely random forest (ERF) method, based on the UCI data experiment. On the moderate training datasets, the IERF algorithm beats the decision tree reconstruction algorithm and other incremental learning algorithms on the performance. Finally, the IERF algorithm is used to solve online video object tracking (multi-object tracking also included) problems, and the results on the challenging video sequences demonstrate its effectiveness and robustness.