Theory of Supersymmetric Quantum Electrodynamics is extended by interactions with external vector and tensor backgrounds, that are assumed to be generated by some Lorentz-violating (LV) dynamics at an ultraviolet scale perhaps related to the Planck scale. Exact supersymmetry requires that such interactions correspond to LV operators of dimension five or higher, providing a solution to the naturalness problem in the LV sector. We classify all dimension five and six LV operators, analyze their properties at the quantum level and describe observational consequences of LV in this theory. We show that LV operators do not induce destabilizing D-terms, gauge anomaly and the Chern-Simons term for photons. We calculate the renormalization group evolution of dimension five LV operators and their mixing with dimension three LV operators, controlled by the scale of the soft-breaking masses. Dimension five LV operators are constrained by the low-energy precision measurements at 10^{-10}-10^{-5} level in units of the inverse Planck scale, while the Planck-scale suppressed dimension six LV operators are allowed by observational data.

37 pages LaTeX, minor revisions, and typos corrected