We study associative memory of an oscillator neural network with distributed native frequencies. The model is based on the use of the Hebb learning rule with random patterns (\(\xi_i^{\mu}=\pm 1\)), and the distribution function of native frequencies is assumed to be symmetric with respect to its average. Although the system with an extensive number of stored patterns is not allowed to get entirely synchronized, long time behaviors of the macroscopic order parameters describing partial synchronization phenomena can be obtained by discarding the contribution from the desynchronized part of the system. The oscillator network is shown to work as associative memory accompanied by synchronized oscillations. A phase diagram representing properties of memory retrieval is presented in terms of the parameters characterizing the native frequency distribution. Our analytical calculations based on the self-consistent signal-to-noise analysis are shown to be in excellent agreement with numerical simulations, confirming the validity of our theoretical treatment.