This paper describes a novel, highly-sensitive ultrasonic Doppler velocity sensing system for low velocity measurement in portable navigation systems. It is a compact velocity sensing system, in which MEMS ultrasonic transducers are incorporated with phase-locked-loop (PLL) circuitry for frequency detection and signal processing. The achieved voltage-velocity sensitivity is 0.22 V/(mm/s) and the minimum detectable velocity is 0.67 mm/s, corresponding to 0.11 Hz in Doppler frequency. To the best of our knowledge, the minimum detectable velocity is the best reported in literature. Also, the output of the PLL is a DC voltage linearly related to the velocity, and there is no need to convert the frequency shift to analog voltage.