This paper presents a novel algorithm for robust object recognition. We propose to model the visual appearance of objects via probability density functions. The algorithm consists of a fully connected Markov random field with energy function derived from results of statistical physics of spin glasses. Markov random fields and spin glass energy functions are combined together via nonlinear kernel functions; we call the model Spin Glass--Markov Random Field. Full connectivity enables to take into account the global appearance of the object, and its specific local characteristics at the same time, resulting in robustness to noise, occlusions and cluttered background. We show with theoretical analysis and experiments that this new model is competitive with state-of-the-art algorithms.