Cryogels based on hydrophobic polymers combining good mechanical properties with fast responsivity are attractive materials for many applications, such as oil spill removal from water and passive sampler for organic pollutants. We present, here, cryogels based on butyl rubber (BR) with a high stretchability, rapid self-recoverability, and excellent reusability for organic solvents. BR cryogels were prepared at subzero temperatures in cyclohexane and benzene at various BR concentrations in the presence of sulfur monochloride (S2Cl2) as a crosslinker. Although the properties of BR cryogels are independent of the amount of the crosslinker above a critical value, the type of the solvent, the cryogelation temperature, as well as the rubber content significantly affect their properties. It was found that benzene produces larger pore volumes as compared to cyclohexane due to the phase separation of BR from benzene at low temperatures, producing additional pores. Increasing cryogelation temperature from -18 to -2 degrees C leads to the formation of more ordered and aligned pores in the cryogels. Increasing BR content decreases the amount of unfrozen microphase of the frozen reaction solution, leading to a decrease in the total porosity of the cryogels and the average diameter of pores. Cryogels formed at -2 degrees C and at 5% (w/v) BR in cyclohexane sustain up to around 1400% stretch ratios. Cryogels swollen in toluene can completely be squeezed under strain during which toluene is released from their pores, whereas addition of toluene to the squeezed cryogels leads to recovery of their original shapes.