We develop a theory of percolation with plasticity media (PWPs) rendering properties of interest for neuromorphic computing. Unlike the standard percolation, they have multiple (N ≫ 1) interfaces and exponentially large number (N!) of conductive pathways between them. These pathways consist of non-ohmic random resistors that can undergo bias induced nonvolatile modifications (plasticity). The neuromorphic properties of PWPs include: multi-valued memory, high dimensionality and nonlinearity capable of transforming input data into spatiotemporal patterns, tunably fading memory ensuring outputs that depend more on recent inputs, and no need for massive interconnects. A few conceptual examples of functionality here are random number generation, matrix-vector multiplication, and associative memory. Understanding PWP topology, statistics, and operations opens a field of its own calling upon further theoretical and experimental insights.