This work presents the design of a robust foam formulation that tolerates harsh reservoir conditions (high salinity, high divalent ion concentration, high temperature, light oil, and hydrocarbon injection gas) in a sandstone reservoir. For this, we selected anionic Alpha Olefin Sulfonate (AOS) surfactants and studied their synergistic effects in mixtures with zwitterionic betaines to enhance foam performance. The laboratory workflow used to define the best formulation followed a de-risking approach in three consecutive phases. First, (phase 1) the main surfactant (AOS) was selected among a series of commercial candidates in static conditions. Then, (phase 2) the betaine booster to be combined with the previously selected AOS was chosen and their ratio optimized in static conditions. Subsequently, (phase 3) the surfactant/booster ratio was optimized under dynamic conditions in a porous medium in the absence and the presence of oil. As a result of this study, a mixture of an AOS C14–C16 and cocamidopropyl hydroxysultaine (CAPHS) was selected as the one having the best performance. The designed formulation was proven to be robust in a wide range of conditions. It generated a strong and stable foam at reservoir conditions, overcoming variations in salinity and foam quality, and tolerated the presence of oil.