The effects of classical gravitational radiation in models with large extra dimensions are investigated for ultra high energy cosmic rays (CRs). The cross sections are implemented into a simulation package (SENECA) for high energy hadron induced CR air showers. We predict that gravitational radiation from quasi-elastic scattering could be observed at incident CR energies above $10^9$ GeV for a setting with more than two extra dimensions. It is further shown that this gravitational energy loss can alter the energy reconstruction for CR energies $E_{\rm CR}\ge 5\cdot 10^9$ GeV.