This study addresses the problem of approximation of calibrations of the phase-fluorimetric oxygen sensors. Three common models of active medium were analysed: single-exponential, single-exponential with non-linear solubility and double-exponential, with and without consideration of possible instrumental errors. The relationship between the quenching constants of the double-exponential and non-linear solubility models was demonstrated. It was shown that all these models can be expressed in one general form, using different dependencies of the quenching constant from the oxygen concentration. This allowed us to suggest a universal algorithm of approximation based on the optimisation of calibration points ([O2],ϕ) in coordinates (k,ϕ). Movement from simple to complex models enables to control the process of optimisation. To determine the best model and its parameters, use of the mean-square and the uniform target functions is suggested. This algorithm was validated with the practical phase-fluorimetric oxygen sensor, where it provided the accuracy of approximation of less than 1% for the oxygen range 0–100kPa. Further improvement was limited by the confidence level of calibration. It was demonstrated that this algorithm can improve the accuracy of the approximation by considering the possible instrumentation errors.