Ultra high-energy cosmic rays (UHECRs) are believed to be protons accelerated in magnetized plasma outflows of extra-Galactic sources. The acceleration of protons to ~10^{20} eV requires a source power L>10^{47} erg/s. The absence of steady sources of sufficient power within the GZK horizon of 100 Mpc, implies that UHECR sources are transient. We show that UHECR flares should be accompanied by strong X-ray and gamma-ray emission, and that X-ray and gamma-ray surveys constrain flares which last less than a decade to satisfy at least one of the following conditions: (i) L>10^{50} erg/s; (ii) the power carried by accelerated electrons is lower by a factor >10^2 than the power carried by magnetic fields or by >10^3 than the power in accelerated protons; or (iii) the sources exist only at low redshifts, z<<1. The implausibility of requirements (ii) and (iii) argue in favor of transient sources with L>10^{50} erg/s.