Over the last few years there has been a growing interest in the domain of pedestrian navigation, stimulated by the increasing demand for Location Based Services. Pedestrian Dead Reckoning (PDR) based on MEMS sensors has been at the heart of most high-end hybrid solutions devised up to now. In PDR mode, the positioning accuracy is shaped by the individual accuracies in step length and azimuth estimation. This paper will focus on how to improve the latter. Measurements from three single axis MEMS gyroscopes, accelerometers, and magnetometers are merged in an Adaptive Extended Kalman Filter to estimate the absolute orientation of a pedestrian. Enhanced performance is accomplished by the online calibration of the gyroscope and accelerometer biases and through the compensation of magnetic perturbations that disturb the magnetometer measurements. Details of this orientation algorithm and assessment of its effectiveness under different testing conditions are presented in this paper.