In this paper, we present the experimental results obtained in the microwave frequency range using an electromagnetic band gap (EMBG) resonator covered with carbon nanotubes(CNTs) and dedicated to CH4 gas detection. The multi-walled CNTs layer is decorated with gold nanoislands (with sizes between 2 nm and 20 nm) and deposited over the EMBG resonator. The microwave measurements of the CNT-based EMBG resonator in air (no gas) and kept for 60 min inside the chamber filled with CH4 demonstrate a shift in the resonance frequency of about 139 MHz and a phase shift of about 9.63°. A very good sensitivity of about 4.58% was obtained from scattering parameters measurements. A new device for CH4 detection was then fabricated and tested.