Nanostructured tellurium thin films have been fabricated and both the DC electrical conductivity and impedance spectra were investigated in different gaseous media. It is shown that the grain dimensionality and properties of the grown Te films are determined by fabrication parameters, such as microstructure of the substrate, the growth rate or post-deposition treatment. As shown by SEM, AFM and XRD, the rate of deposition most strongly influences the microstructure of the films and their gas sensing properties. An increase of the rate results in the transformation of the microcrystalline structure of the film to a nanostructured one, or even to an amorphous state. It is pointed out that the nanostructured tellurium films exhibit sensitivity at room temperature not only to nitrogen dioxide [1] or hydrogen sulfide [2], but also to combustible and low - reactive gases such as H2 and CO2. Exposure to toxic gases results in the both variation of the DC conductivity and impedance of nanostructured thin Te films. Due to impedance change in different directions the reducing gases, such as H2S or H2 may be distinguished from oxidizing NO2 or CO2 ones, hence the effective and selective sensors, operating at room temperature can be manufactured using the nanostructured tellurium films.