During the past few decades, two and higher dimensional systems have been extensively applied in many areas of research. The representation of the 2-D systems in the frequency domain is usually given by its transfer function. The bounded-input bounded-output (BIBO) stability of the two dimensional discrete systems depends on the zeros of the characteristic polynomial which is the denominator of this transfer function. In this paper, a new sufficient criterion for the stability of two-dimensional linear shift-invariant discrete systems is presented. The new criterion is based on the sufficient condition for stable polynomials with complex coefficients and the stability criterion for 2-D discrete systems proposed by Murray and Delsarte et al. The new criterion is non-conservative for the stability testing of 2-D discrete systems. It is shown that the proposed sufficient criterion is simple enough to be applied for the stability checking of the 2-D discrete systems. The utility of the proposed criterion is demonstrated by examples. © 2013 IEEE.