False data injection attack (FDIA) is a critical cyber-attack that can cause disrupt operations and subsequently blackouts in smart grid networks. Cleverly constructed stealthy false measurement vectors can circumvent the bad data detector unit and mislead the state estimation process. This article proposes a novel belief propagation (BP)-based algorithm to detect both random and stealthy-type FDIAs in smart grids with higher detection rate than the state-of-the-art machine learning classifiers such as Naive Bayes, support vector machines, Random Forest, OneR, and AdaBoost. Another novel feature of the proposed algorithm is to detect FDIAs without using any historical cyber-attack data, which are sketchy due to security constraints and infinitesimal in occurrence numbers. The proposed BP method utilizes local sensor measurement data to calculate local belief and send it as a message signal to the control center. Then, the control center determines final/global belief and compares the result with a predefined threshold value derived from the uncompromised measurement database. The real-time steady-state load data are utilized for dc state estimation. From the obtained results, performance parameters such as detection rate, receiver operating characteristic curve, precision, recall, and F-measure of the proposed BP algorithm are found superior to the aforementioned state-of-the-art machine learning algorithms.