Non-invasive assessment of arterial stiffness through pulse wave velocity (PWV) analysis is becoming common clinical practice. However, the effects of measurement noise, temporal resolution and similarity of the two waveforms used for PWV calculation upon accuracy and variability are unknown. We studied these effects upon PWV estimates given by foot-to-foot, least squared difference, and cross-correlation algorithms. We assessed accuracy using numerically generated blood pressure and flow waveforms for which the theoretical PWV was known to compare with the algorithm estimates. We assessed variability using clinical measurements in 28 human subjects. Wave shape similarity was quantified using a cross correlation-coefficient (CCCoefficient), which decreases with increasing distance between waveform measurements sites. Based on our results, we propose the following criteria to identify the most accurate and least variable algorithm given the noise, resolution and CCCoefficient of the measured waveforms. (1) Use foot-to-foot when the noise-to-signal ratio ≤10%, and/or temporal resolution ≥100 Hz. Otherwise (2) use a least squares differencing method applied to the systolic upstroke.