We report on an all-sky search with the LIGO detectors for periodic gravitational waves in the frequency range 50–1000 Hz and with the frequency’s time derivative in the range −1×10^−8Hz s^-1 to zero. Data from the fourth LIGO science run (S4) have been used in this search. Three different semicoherent methods of transforming and summing strain power from short Fourier transforms (SFTs) of the calibrated data have been used. The first, known as StackSlide, averages normalized power from each SFT. A “weighted Hough” scheme is also developed and used, which also allows for a multi-interferometer search. The third method, known as PowerFlux, is a variant of the StackSlide method in which the power is weighted before summing. In both the weighted Hough and PowerFlux methods, the weights are chosen according to the noise and detector antenna-pattern to maximize the signal-to-noise ratio. The respective advantages and disadvantages of these methods are discussed. Observing no evidence of periodic gravitational radiation, we report upper limits; we interpret these as limits on this radiation from isolated rotating neutron stars. The best population-based upper limit with 95% confidence on the gravitational-wave strain amplitude, found for simulated sources distributed isotropically across the sky and with isotropically distributed spin axes, is 4.28×10^-24(near 140 Hz). Strict upper limits are also obtained for small patches on the sky for best-case and worst-case inclinations of the spin axes.