Cellular Automata (CAs), a ubiquitous computational tool proposed by John von Neumann, illustrate how great complexity emerges from simple rules of dynamical transitions between space and time interconnected simplistic entities. CAs perform as mathematical computation models, but also they are a powerful medium to model nature and natural systems. As a computational platform, CAs come with unified memory and computation in the same physical area, attributed as a strong candidate against the limitations of data transfer, known as the von Neumann bottleneck. On the other hand, Memristors with their inherent Computing-In-Memory compatibility, can be easily considered as appropriate nanoelectronic devices to be coupled with CAs towards an energy and time efficient computational paradigm. In particular, CA present a vast area of applications, comprising various NP-complete hard to be solved problems arriving from computer science field, like the well-known Shortest Path, Bin Packing, Knapsack and Max-clique problems, as well as physical, chemical and biological processes and phenomena, such as epileptic seizures in relation with healthy and pathogenic brain regions and, moreover, real life applications like pseudorandom number generation and simplistic, but with highly complex behavior, models like the famous Game of Life. The outcome of employing Memristors in CAs applications is promising in terms of parallelization, power consumption, scalability, reconfigurability, and high computing performance.