Gamma-ray induced air showers are notable for their lack of muons, compared to hadronic showers. Hence, air shower arrays with large underground muon detectors can select a sample greatly enriched in photon showers by rejecting showers containing muons. IceCube is sensitive to muons with energies above ∼500  GeV at the surface, which provides an efficient veto system for hadronic air showers with energies above 1 PeV. One year of data from the 40-string IceCube configuration was used to perform a search for point sources and a Galactic diffuse signal. No sources were found, resulting in a 90% C.L. upper limit on the ratio of gamma rays to cosmic rays of 1.2×10−3 for the flux coming from the Galactic plane region (−80°≲l≲−30°; −10°≲b≲5°) in the energy range 1.2–6.0 PeV. In the same energy range, point source fluxes with E−2 spectra have been excluded at a level of (E/TeV)2dΦ/dE∼10−12–10−11  cm−2 s−1 TeV−1 depending on source declination. The complete IceCube detector will have a better sensitivity (due to the larger detector size), improved reconstruction, and vetoing techniques. Preliminary data from the nearly final IceCube detector configuration have been used to estimate the 5-yr sensitivity of the full detector. It is found to be more than an order of magnitude better, allowing the search for PeV extensions of known TeV gamma-ray emitters.