This paper considers the problem of online calibration and recalibration of continuous glucose monitoring devices. A parametric relation between interstitial and blood glucose is investigated and a constructive algorithm to adaptively estimate the parameters within this relation is proposed. The algorithm explicitly considers measurement uncertainty of the device used to collect the calibration measurements and enables automatic detection of measurements which are not suitable to be used for calibration. The method was assessed on clinical data from 17 diabetic patients and the improvements with respect to the current state of the art is shown. © 2013 IEEE.