We present the first search for heavy, long-lived particles that decay to photons at a hadron collider. We use a sample of gamma+jet+missing transverse energy events in p (p) over bar collisions at root s=1.96 TeV taken with the CDF II detector. Candidate events are selected based on the arrival time of the photon at the detector. Using an integrated luminosity of 570 pb(-1) of collision data, we observe 2 events, consistent with the background estimate of 1.3 +/- 0.7 events. While our search strategy does not rely on model-specific dynamics, we set cross section limits in a supersymmetric model with (chi) over tilde (0)(1)->gamma(G) over tilde and place the world-best 95% C.L. lower limit on the (chi) over tilde (0)(1) mass of 101 GeV/c(2) at tau(0)((chi) over tilde1)=5 ns.