We apply two different algorithms to measure surface wave phase velocity, as a function of frequency, from seismic ambient noise recorded at pairs of stations from a large European network. The two methods are based on consistent theoretical formulations, but differ in the implementation: one method involves the time-domain cross-correlation of signal recorded at different stations; the other is based on frequency-domain cross-correlation, and requires finding the zero-crossings of the real part of the cross-correlation spectrum. Furthermore, the time-domain method, as implemented here and in the literature, practically involves the important approximation that interstation distance be large compared to seismic wavelength. In both cases, cross-correlations are ensemble-averaged over a relatively long period of time (1 yr). We verify that the two algorithms give consistent results, and infer that phase velocity can be successfully measured through ensemble-averaging of seismic ambient noise, further validating earlier studies that had followed either approach. The description of our experiment and its results is accompanied by a detailed though simplifed derivation of ambient-noise theory, writing out explicitly the relationships between the surface wave Green’s function, ambient-noise cross-correlation and phase and group velocities.