This paper addresses the problem of complete stability analysis for cellular neural networks (CNN's) with variable delays. The M-matrix theory and new analysis techniques are utilized to establish novel delay-independent/delay- dependent sufficient conditions under which the complete stability of CNN's with variable delays can be guaranteed. The new stability criteria do not require any symmetric condition of the feedback matrix and the delayed feedback matrix, thus being much widely applicable. The developed theoretical results are further illustrated by numerical examples, including their superiority over the existing results.