We propose a scheme for parameter estimation with cluster states. We find that phase estimation with cluster states under a many-body Hamiltonian and separable measurements leads to a precision at the Heisenberg limit. As noise models we study the dephasing, depolarizing, and pure damping channels. Decoherence reduces the sensitivity but our scheme remains superior over several reference schemes with states such as maximally entangled states and product states. For small cluster states and fixed evolution times it remains at the Heisenberg limit for approximately 2 times as many qubits than alternative schemes.