The key point here is that your body does not measure blood oxygen levels. Instead, the urge to breathe is caused by a surplus of carbon dioxide in your blood. At sea level, this is fine: the only way to get so much carbon dioxide in your blood is if you used up all the oxygen.
At higher altitudes, the pressure is lower, and consequently the oxygen partial pressure. Since the rate of diffusion in your lungs is a function of pressure, this means that oxygen will diffuse less readily into your blood. At the same time, carbon dioxide diffuses more readily out of your blood due to the low pressure. This reduces your urge to breathe; you do not feel 'out of breath'. See this Wikipedia page.
At even higher altitudes, the pressure is actually so low that breathing will cause oxygen to diffuse out of your blood; you can breathe as much as you want but the partial pressure of oxygen in your blood will never be higher than the partial oxygen pressure in the air. This is why oxygen masks work (even if they're not airtight): they replace all air near your nose and mouth with oxygen, so that the partial pressure of oxygen equals the total atmospheric pressure rather than the usual ~21%. See this and this Wikipedia page, or for example this YouTube video.
Somewhat related: at sea level, you can also run out of oxygen before you feel the urge to breathe. You might think that breathing deeply before having to hold your breath for a long time increases the amount of oxygen in your blood, increasing your endurance. This is only partially true: it also artificially reduces your carbon dioxide levels, reducing your urge to breathe. This way, you can black out before feeling out of breath, which can be dangerous under water!