Falsification detection is a critical advance in ensuring that real-time information about vehicles and their movement states is certified on the Internet of Vehicles (IoV). Thus, detecting nodes that are propagating inaccurate information is a requirement for the successful deployment of IoV services although only a few research studies have been carried out on Basic Safety Message (BSM) falsification. As such, this paper proposes a Randomized Search Optimization Ensemble-based Falsification Detection Scheme (RSO-FDS). The RSO technique was used to construct the proposed Ensemble-based Random Forest (RF) model. The evaluation was performed on three different datasets developed to evaluate falsification in IoV. In addition, the six most popular supervised learning (SL) algorithms were investigated to evaluate the capability of the proposed RSO-FDS, which had the best performance across all datasets. The performance metrics considered are computational efficiency in terms of prediction time, validation accuracy for overall attack classification, precision, recall, and F1 scores. For validation, the performance of the proposed RSO-FDS was further compared with results from recent works. Furthermore, the irrelevance of data balancing was illustrated for real-life IoV scenarios. The result shows that the proposed model outperformed state-of-the-art algorithms implemented in this work and related works.