This paper reports on the use of online data stream classification algorithms to support workload orchestration in vehicular edge computing environments. These algorithms can be used to predict the ability of available computational nodes to successfully handle computational tasks generated from vehicular applications. Several online data stream classification algorithms have been evaluated based on synthetic datasets generated from simulated vehicular edge computing environments. In addition, a multi-criteria decision analysis technique was utilized to rank the different algorithms based on their performance metrics. The evaluation results demonstrate that the considered algorithms can handle online classification operations with various trade-offs and dominance relations with respect to their obtained performance. In addition, the utilized multi-criteria decision analysis technique can efficiently rank various algorithms and identify the most appropriate algorithms to augment workload orchestration. Furthermore, the evaluation results show that the leveraging bagging algorithm, with an extremely fast decision tree base estimator, is able to maintain marked online classification performance and persistent competitive ranking among its counterparts for all datasets. Hence, it can be considered a promising choice to reinforce workload orchestration in vehicular edge computing environments.