Background estimation, i.e. automatic recovery of the background image from a sequence of images containing moving foreground objects, is an important module in many applications, e.g. surveillance and video segmentation. In this paper, we present a simple, yet effective and robust approach for background estimation based on Loopy Belief Propagation. Robustness of the proposed approach means: (i) minimal assumption on the input frames, and (ii) no need to tune parameters. Basically, the background can be recovered even when the occluding foreground objects stay still for a long time. Furthermore, no motion information needs to be known or estimated for the foreground objects, which implies that background can be recovered from a set of frames which are not consecutive temporally. Analysis and experiments are provided to compare the proposed approach to related methods. Experimental results on typical surveillance videos demonstrate the effectiveness of our approach.