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 x 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)^2 dՓ/dE ~ 10^-12 -10^-11 cm^-2s^-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.