In this study, attention is paid to oxygen dissolution in the metallic matrix, i.e., pure titanium (α-Ti) and niobium-alloyed titanium (α- and β-Ti) during exposure at 800°C in dry and humidified argon/oxygen and nitrogen/oxygen atmospheres. In particular, the diffusion coefficients and the total amount of oxygen in both materials have been determined by profiling micro-hardness in the matrix after oxidation. Experimental data showed that even after oxidation in nitrogen-containing atmospheres, the amount of dissolved nitrogen in pure and niobium-alloyed titanium was significantly lower than the amount of oxygen. This justifies that only oxygen should be considered as the dissolved species. It is shown that micro-hardness data are very useful for diffusion studies. Microhardness values, obtained from a one-phase material, i.e., pure titanium (α-phase), can be “curve-fit” by a simple error function. However, concerning a two-phase material, i.e., Ti–4Nb (α- and β-titanium) a modification of the simple error-function approach is needed, resulting in an adapted function consisting of two different error functions combined with a prefactor, indicating the relative contribution of each phase. From the available data, it was determined that the diffusion coefficient of oxygen in α-Ti is about two orders of magnitude higher than in β-Ti.