Most oxygen required to support the energy needs of vertebrate tissues is delivered by diffusion from microvessels. The presence of red blood cells (RBCs) makes blood flow in the microcirculation highly heterogeneous. Additionally, flow regulation mechanisms dynamically respond to changes in tissue energy demand. These spatio-temporal variations directly affect the supply of oxygen to parenchymal cells. Due to various limiting assumptions, current models of oxygen transport cannot fully capture the consequences of complex hemodynamic effects on tissue oxygenation, and are often not suitable for studying unsteady phenomena. With our new approach based on moving RBCs, the impact of blood flow heterogeneity on oxygen partial pressure (PO2) in the tissue can be quantified. Oxygen transport was simulated using parachute-shaped solid RBCs flowing through a capillary. Using a conical tissue domain with radii 19 μm and 13 μm respectively, our computations indicate that PO2 at the RBC membrane exceeds PO2 between RBCs by 30 mmHg on average, and that the mean plasma PO2 decreases by 9 mmHg over 50 μm. These results reproduce well recent intravascular PO2 measurements in the rodent brain. We also demonstrate that instantaneous variations of capillary hematocrit cause associated fluctuations of tissue PO2. Further, our results suggest that homogeneous tissue oxygenation requires capillary networks to be denser on venular side than on arteriolar side. Our new model for oxygen transport will make it possible to quantify in detail the effects of blood flow heterogeneity on tissue oxygenation in realistic capillary networks.