We report experimental studies of the effect of interstitial gas on mass-density segregation in a vertically vibrated mixture of equal-sized bronze and glass spheres. Sufficiently strong vibration in the presence of interstitial gas induces vertical segregation into sharply separated bronze and glass layers. We find that the segregated steady state (i.e., bronze or glass layer on top) is a sensitive function of gas pressure and viscosity, as well as vibration frequency and amplitude. In particular, we identify distinct regimes of behavior that characterize the change from bronze-on-top to glass-on-top steady state.