An air stream is compressed in multiple stages using refrigeration derived from a refrigerant comprising natural gas for inter-stage cooling. The possibility of natural gas leaking into the air stream is reduced by use of an intermediate cooling medium (“ICM”) to transfer the refrigeration from the refrigerant to the inter-stage air stream. The compressed air stream can be fed to a cryogenic air separation unit that includes an LNG-based liquefier unit from which a cold natural gas stream is withdrawn for use as said refrigerant.