A photonic quasi-crystal fiber (PQF) methane sensor based on surface plasmon resonance (SPR) is designed and described. The double-side polished six-fold photonic quasi-crystal fiber coated with a silver film produces enhanced SPR effects and sensitivity. A nanostructured thin film with cryptophane-E-doped polysiloxane is deposited on silver as the methane-sensitive surface layer and to mitigate oxidation of silver. The sensor is analyzed and optimized numerically by the full-vector finite element method. For methane concentrations in the range of 0% to 3.5%, the maximum sensitivity of the sensor is 8 nm/%, and the average sensitivity is 6.643 nm/%. Compared to traditional gas sensors, this sensor provides accurate sensing of methane besides offering advantages such as the low cost, miniaturized size, online monitoring, and immunity to electromagnetic field interference.