Understanding flame quenching is needed to develop efficient flame arresters. Here, the quenching distance of methane-air laminar flames is measured at atmospheric pressure for temperatures of the quenching surface down to the cryogenic, Tw = 138 K to 293 K, for two configurations: head-on and tube quenching. Fuels or flammable mixtures in contact with surfaces at temperatures below 293 K are, for example, representative of aircraft during cruise, cryogenic rocket engines, fuel distribution pipes at high altitude, or cryogenic storage of liquified natural gas and hydrogen. The experimental methods are first validated for Tw = 293 K by comparing measured quenching distances to that available in the literature. Then, quenching distances are measured for Tw = 138 K to 293 K. The quenching distance increases when temperature decreases. In the head-on quenching configuration, the quenching distance is almost multiplied by two, from δq = 0.17 mm for Tw = 290 K to δq = 0.32 mm for Tw = 175 K. In the tube quenching configuration, the quenching diameter increases by 40%, from 2.5 mm for Tw = 293 K to 3.5 mm for Tw = 138 K. Experiments conducted in tubes demonstrate that reducing the wall temperature allows quenching with larger tube diameters, yielding lower pressure drops in tubes, which is of practical interest.