In this paper we characterize a class of self-similar non-Gaussian Markov Random Fields (MRFs) that we call Critical MRFs (CMRFs). We show that since the partition function in a Gibbs distribution of a CMRF is necessarily scale invariant, all order statistics generated from the partition function take a power-law form. This implies that the correlation function has long-range memory since it decays as a power-law function, a very important characteristic of many textures. This characterization is potentially of great use in modeling a wide variety of multi-dimensional spatial phenomena.