New Findings: What is the central question of this study? The pulmonary oxygen uptake ((Formula presented.)) data used to study the muscle aerobic system dynamics during moderate-exercise transitions is classically described as a mono-exponential function controlled by a complex interaction of the oxygen delivery–utilization balance. This elevated complexity complicates the acquisition of relevant information regarding aerobic system dynamics based on (Formula presented.) data during a varying exercise stimulus. What is the main finding and its importance? The elevated complexity of (Formula presented.) dynamics is a consequence of a multiple-order interaction between muscle oxygen uptake and circulatory distortion. Our findings challenge the use of a first-order function to study the influences of the oxygen delivery–utilization balance over the (Formula presented.) dynamics. The assumption of aerobic system linearity implies that the pulmonary oxygen uptake ((Formula presented.)) dynamics during exercise transitions present a first-order characteristic. The main objective of this study was to test the linearity of the oxygen delivery–utilization balance during random moderate exercise. The cardiac output ((Formula presented.)) and deoxygenated haemoglobin concentration ([HHb]) were measured to infer the central and local O2 availability, respectively. Thirteen healthy men performed two consecutive pseudorandom binary sequence cycling exercises followed by an incremental protocol. The system input and the outputs (Formula presented.), [HHb] and (Formula presented.) were submitted to frequency-domain analysis. The linearity of the variables was tested by computing the ability of the response at a specific frequency to predict the response at another frequency. The predictability levels were assessed by the coefficient of determination. In a first-order system, a participant who presents faster dynamics at a specific frequency should also present faster dynamics at any other frequency. All experimentally obtained variables ((Formula presented.), [HHb] and (Formula presented.)) presented a certainly degree of non-linearity. The local O2 availability, evaluated by the ratio (Formula presented.) /[HHb], presented the most irregular behaviour. The overall [HHb] kinetics were faster than (Formula presented.) and (Formula presented.) kinetics. In conclusion, the oxygen delivery–utilization balance behaved as a non-linear phenomenon. Therefore, the elevated complexity of the pulmonary oxygen uptake dynamics is governed by a complex multiple-order interaction between the oxygen delivery and utilization systems.