We study deformations of maximally supersymmetric gauge theories by higher dimensional operators in various spacetime dimensions. We classify infinitesimal deformations that preserve all 16 supersymmetries, while allowing the possibility of breaking either Lorentz or R-symmetry, using an on-shell algebraic method developed by Movshev and Schwarz. We also consider the problem of extending the deformation beyond the first order.