The classification of Lorentz- and C P T -violating operators in non-Abelian gauge field theories is performed. We construct all gauge-invariant terms describing propagation and interaction in the action for fermions and gauge fields. Restrictions to the Abelian, Lorentz-invariant, and isotropic limits are presented. We provide two illustrative applications of the results to quantum electrodynamics and quantum chromodynamics. First constraints on nonlinear Lorentz-violating effects in electrodynamics are obtained using data from experiments on photon-photon scattering, and corrections from nonminimal Lorentz and C P T violation to the cross section for deep inelastic scattering are derived.