In this study, the impact of impurities/mixtures in CO2 streams during the CO2 injection process as an enhanced oil recovery technique in heavy oil formations was examined. For this purpose, detailed theoretical and experimental studies were conducted to explore the possible effect of impurities/mixtures on the performance and recovery mechanisms of the injection process. Three different mixtures of CH4–CO2 with a CH4 concentration of 15, 30 and 50%, N2–CO2 with an N2 concentration of 15%, and N2–CH4–CO2 with an N2–CH4 concentration of 15–25% were used. First, a thorough phase behavior analysis of the heavy crude oil–CO2 impurities/mixtures was conducted. The solubility of each mixture in heavy oil was measured and the results showed that among CH4–CO2 and N2–CO2 mixtures, CH4–CO2 is more soluble in the heavy oil sample. However, pure CO2 is more soluble than CH4–CO2 and N2–CO2 and the presence of N2 in the CO2 mixture reduces the solubility the most. Moreover, it was observed that the solubility of mixtures increased as pressure increased while declined as the temperature increased. Thereafter, a series of pure and impure CO2 injection tests were designed and carried out at a constant temperature of T = 21 oC and constant operating pressure of Pop = 4.48 MPa. The results indicated that pure CO2 is able to recover 28–30% of OOIP, while 26–27% and 24–25% of OOIP was produced during the injection of CH4–CO2 and N2–CO2 mixtures, respectively. From the enhanced oil recovery point of view, it is unfortunate that the oil recovery factor was not improved at the given operating pressure and temperature. The inclusion of impurities in pure CO2 reduces solubility and, consequently, the oil recovery decreases during the injection process.