We report a direct lattice calculation of the $K$ to $\pi\pi$ decay matrix elements for both the $\Delta I=1/2$ and 3/2 amplitudes $A_0$ and $A_2$ on 2+1 flavor, domain wall fermion, $16^3\times32\times16$ lattices. This is a complete calculation in which all contractions for the required ten, four-quark operators are evaluated, including the disconnected graphs in which no quark line connects the initial kaon and final two-pion states. These lattice operators are non-perturbatively renormalized using the Rome-Southampton method and the quadratic divergences are studied and removed. This is an important but notoriously difficult calculation, requiring high statistics on a large volume. In this paper we take a major step towards the computation of the physical $K\to\pi\pi$ amplitudes by performing a complete calculation at unphysical kinematics with pions of mass 422\,MeV at rest in the kaon rest frame. With this simplification we are able to resolve Re$(A_0)$ from zero for the first time, with a 25% statistical error and can develop and evaluate methods for computing the complete, complex amplitude $A_0$, a calculation central to understanding the $\Delta =1/2$ rule and testing the standard model of CP violation in the kaon system.