Recommender systems enable service providers to predict and address the individual needs of their customers so as to deliver personalized experiences. In this paper, we formulate the recommendation problem as an inference problem on a Pairwise Markov Random Field (PMRF), where nodes representing items are connected with each other to exploit item-based similarity. However, direct prediction of ratings has exponential time complexity, as it requires to compute marginal probabilities. Thus, we utilize the Belief Propagation (BP) algorithm to solve the problem with a complexity that grows linearly with the number of items in the system. The BP algorithm computes marginal probabilities by performing iterative probabilistic message-passing between item nodes on the PMRF. One desirable feature of the proposed scheme is that it does not require to solve the problem for all users if it wishes to update the recommendations for only a single active user. Moreover, its complexity remains linear per active user. Via computer simulations using 100 K MovieLens dataset, we verify that the proposed algorithm outperforms the MovieAvg and Pearson Correlation Coefficient (PCC) algorithms in terms of both Root Mean Squared Error (RMSE) and Mean Absolute Error (MAE).