The fundamental properties of dark matter can affect structure formation in our Universe in subtle ways. Unfortunately, many dark matter theories make similar predictions for how structure assembles on large and small scales, leading to a large degeneracy in model space. Motivated by this, we formulate an effective theory of structure formation (ETHOS) that enables cosmological structure formation to be computed in a vast array of microphysical model of dark matter physics. This framework maps the detailed microphysical theories of particle dark matter interactions into the physical effective parameters that shape the linear matter power spectrum and the self-interaction transfer cross section of non-relativistic dark matter. These are the input to structure formation simulations, which follow the evolution of the cosmological and galactic dark matter distributions. These effective parameters in ETHOS allow the classification of dark matter theories according to their structure formation properties rather than their intrinsic particle properties, paving the way for future simulations to span the space of viable dark matter physics relevant for structure formation. We discuss how this framework can help understanding how dark matter microphysics affects structure formation on small scales.