Matrix factorization (MF) is the simplest and most well studied factor based model and has been applied successfully in several do- mains. One of the standard ways to solve MF is by finding maximum a posteriori estimate of the model parameters, which is equivalent to minimizing the regularized objective function. Stochastic gradient descent (SGD) is a common choice to minimize the regularized objective function. However, SGD suffers from the problem of overfitting and entails tedious job of finding the learning rate and regularization parameters. A fully Bayesian treatment of MF avoids these problems. However, the existing Bayesian matrix factorization method based on the Markov chain Monte Carlo (MCMC) technique has cubic time complexity with respect to the target rank, which makes it less scalable. In this paper, we propose the Scalable BayesianMatrix Factorization (SBMF), which is a MCMC Gibbs sampling algorithm for MF and has linear time complexity with respect to the target rank and linear space complexity with respect to the number of non-zero observations. Also, we show through extensive experiments on three sufficiently large real word datasets that SBMF incurs only a small loss in the performance and takes much less time as compared to the baseline method for higher latent dimension. Copyright © 2015 by the paper's authors.