An important component of any chemiresistive gas sensor is the way in which the resistance of the sensing film is interrogated. The geometrical structure of an electrode can enhance the performance of a gas-sensing device and in particular the performance of sensing films with large surface areas, such as carbon nanotubes. In this study, we investigated the influence of geometrical structure on the performance of gas sensors, combining the characteristics of carbon nanotubes with a novel gas sensor electrode structure based on fractal geometry. The fabricated sensors were tested with exposure to nitric oxide, measuring both the sensor resistance and capacitance (RC) of the sensor responses. Experimental results showed that the sensors with fractal electrode structures had a superior performance over sensors with traditional geometrical structures. Moreover, the RC characteristics of these fractal sensors could be further improved by using different test frequencies that could aid in the identification and quantification of a target gas.