I have inverted the recently completed set of seismic arrival times from the Apollo lunar seismic network to estimate the average seismic velocities in three sections of the lunar mantle: two for the upper mantle and one for the middle mantle. The method used is a variation of the linearized least squares inversion where the inversion is accomplished in steps. The estimated average velocities in the upper mantle decrease from Vp=7.74 km/s and Vs=4.49 km/s in the section above 270-km depth to Vp=7.46 km/s and Vs=4.25 km/s in the section between 270- and 500-km depth, confirming the earlier finding of negative gradients based on seismic amplitude variations. The average velocities in the middle mantle between the depths of 500 km and 1000 km of Vp=8.26 km/s and Vs=4.65 km/s are significantly higher than those in the upper mantle, contradicting earlier estimates based on more limited data. The higher velocities may suggest initial melting of the moon down to at least 1000-km depth.