Current spectral simulations of Einstein's equations require writing the system in first-order form, potentially introducing instabilities and inefficiencies. This work presents a new penalty method for pseudo-spectral evolutions of second order in space wave equations. The penalties are constructed as functions of Legendre polynomials and are added to the equations of motion everywhere, not only on the boundaries as is typical in first-order formulations. Semi-discrete stability of the new method is proved using energy arguments for the scalar wave equation in flat space, and the generalization to the scalar wave on a curved background is derived. Evolutions of the second order Einstein equations in generalized harmonic form are also explored. Numerical results for multi-domain second order scalar wave and single black hole evolutions demonstrate stability and convergence . The application of the new techniques to the evolution of a 16 orbit, equal mass black hole binary is currently underway. Preliminary results are discussed, which at this time show good performance for approximately the first 10 orbits, after which the evolutions become unstable. However, the findings suggest that these difficulties can be overcome, and that the new second order penalty method will soon become a viable alternative to first order spectral evolutions of Einstein's equations.