It is well known that the number of edge-labeled perfect matchings of a 2 × n planar grid graph is the (n + 1)st Fibonacci number. The number of edge-labeled perfect matchings of grid graphs on surfaces has been computed using Pfaffians, matching polynomials, and generating functions. Here we present an elegant and elementary approach to enumerating edge-labeled perfect matchings of n grid graphs on surfaces representable by opposite-edge-identified quadrilaterals. For simplicity in description, we give proofs using the language of tilings of grids.