We demonstrate that the prethermal regime of periodically-driven, classical many-body systems can host non-equilibrium phases of matter. In particular, we show that there exists an effective Hamiltonian, which captures the dynamics of ensembles of classical trajectories, despite the breakdown of this description at the single trajectory level. In addition, we prove that the effective Hamiltonian can host emergent symmetries protected by the discrete time-translation symmetry of the drive. The spontaneous breaking of such an emergent symmetry leads to a sub-harmonic response, characteristic of time crystalline order, that survives to exponentially late times. To this end, we numerically demonstrate the existence of prethermal time crystals in both a one-dimensional, long-range interacting spin chain and a nearest-neighbor spin model on a two-dimensional square lattice.