Inorganic–organic nanocomposite hybrids containing zirconium dioxide (ZrO2) as inorganic cross-linker/filler and polydimethylsiloxane (PDMS) as a polymeric matrix have been synthesized using the in situ sol–gel reaction between silanol-terminated PDMS and zirconium normal butoxide (Zr(OC4H9)4). Hybrid materials were used to fabricate gas separation membranes which were characterized by scanning electron microscopy, dynamic scanning calorimetry, nanoindentation, ATR-FTIR, and XPS spectroscopies. Amorphous structure of incorporated ZrO2 fillers was verified by X-ray diffraction. Small gases (He, H2, O2, N2, and CO2) permeability experiments were carried out to study the effect of the inorganic component amount on the properties of the ZrO2@PDMS hybrids. The permeability of the developed hybrids considerably exceeded the permeability of conventional PDMS which is known as “gold standard” highly gas-permeable rubbery polymer. Depending on the ZrO2 content, fabricated hybrids demonstrated increased permeability for all gases with improvement inversely proportional to the kinetic diameter of gas molecules, that is, highest permeability increase (relatively to PDMS) was observed for H2 and lowest for N2. Such behavior suggests the formation of the size-sieving amorphous zirconia domains within PDMS which do not impede gas transport due to the nanosize of the fillers. As a result, gas separation membranes prepared using the developed materials demonstrated better separation performance for CO2/N2, H2/N2, and O2/N2 pairs compared to the conventional PDMS.