Dans les années 1940, Stanislaw Ulam étudiait la croissance des cristaux au Laboratoire national de Los Alamos, en la modélisant sur une grille. Dans le même temps, John von Neumann, collègue d'Ulam à Los Alamos, travaillait sur des systèmes auto-réplicatifs et rencontrait des difficultés pour expliciter son modèle initial d'un robot qui se copierait tout seul à partir d'un ensemble de pièces détachées. Ulam lui suggéra de s'inspirer de ses travaux, ce qui conduisit von Neumann à concevoir un modèle mathématique abstrait pour son problème. Le résultat fut le « copieur et constructeur universel » (universal copier and constructor en anglais), le premier automate cellulaire : il était basé sur une grille à deux dimensions où chaque cellule pouvait prendre 29 états. Von Neumann y construisit un motif particulier et démontra qu'il pouvait produire sans fin des copies de lui-même.
En 1969, G. A. Hedlund publie Endomorphisms and Automorphisms of the Shift Dynamical System, une monographie de 60 pages environ qui synthétise 10 ans de recherche d'une communauté travaillant dans le domaine de la dynamique symbolique (une branche de l'étude des systèmes dynamiques en mathématiques, fondée notamment par M. Morse et G. A. Hedlund). C'est cette publication qui pose les bases mathématiques de l'étude des automates cellulaires comme des systèmes dynamiques particuliers.
En 1969 également, Konrad Zuse publia Rechnender Raum (« Quand l'espace calcule») où il émettait l'hypothèse que les lois physiques étaient discrètes et que l'Univers était le résultat d'un gigantesque automate cellulaire.
Dans les années 1970, un automate cellulaire à deux dimensions et deux états nommé « le jeu de la vie », inventé par John Conway, connut un grand succès, particulièrement parmi la communauté informatique naissante. Il fut popularisé par Martin Gardner dans un article du Scientific American.
En 1983, Stephen Wolfram publia la première d'une série de publications où il analysait de façon systématique un type d'automates cellulaires très simples. La complexité de leur comportement, induit par des règles élémentaires, le poussa à conjecturer que des mécanismes similaires pourraient expliciter des phénomènes physiques complexes, idées qu'il développa dans son livre A New Kind of Science paru en 2002.
Cette classification fut introduite par Stephen Wolfram en 1983 dans son article Universality and complexity in cellular automata et représente la première tentative pour classifier les automates cellulaires d'après leur évolution à partir de configurations initiales aléatoires. Il proposa quatre classes de comportement :
Une des critiques de la classification de Wolfram réside dans son impossibilité à dire si un automate cellulaire donné est ; d'ailleurs, des automates cellulaires universels ont été trouvés pour chacune des classes proposées par Wolfram. Cet état de fait provient de ce que Wolfram n'a considéré que des conditions initiales aléatoires, mais pas des structures particulières créées spécifiquement pour l'occasion. En particulier, la transmission d'information, par exemple par l'intermédiaire de vaisseaux, n'est pas prise en compte.
David Eppstein a proposé une alternative a cette classification :
A priori, seuls les derniers cas permettent l'universalité, même si tous les automates cellulaires qui y répondent ne le sont pas. En revanche, il n'a pas été non plus démontré qu'il est impossible de construire des structures universelles pour les autres cas, d'autres structures que les vaisseaux pouvant également transmettre des informations.