A method and apparatus for measuring Quality-of-Service (QoS) in packet-based communications networks for Voice-over-IP applications is advantageously based not only on packet loss information but also on particular characteristics of the speech data itself. Measurement of failures of the "quasi-stationary" (QS) property of speech--that is, the assumption that both the pitch and spectral envelop usually vary slowly relative to the packet size--are advantageously used in conjunction with measures of packet loss characteristics (e.g., packet loss rates or burst ratios) to calculate a QoS measure. One specific QS failure measure--referred to herein as QSFE (quasi-stationary failure estimate)--advantageously estimates the phoneme rate and is used in one illustrative method for calculating a QoS measure for Voice-over-IP applications in the presence of packet loss.