To utilize the manipulation of wave properties by metamaterials, in this paper, a microstrip-fed patch antenna array, loaded with metamaterial superstrate, has been proposed. Under unloaded conditions, the conventional patch antenna array resonates at IEEE 802.16a 5.8 GHz Wi-MAX band with gain of 4.31 dBi and bandwidth of 425 MHz, whereas when each patch of this array is loaded with a metamaterial superstrate, composed with the pair of circular split ring resonators and wire strips, gain and bandwidth approaches to 11.9 dBi and 685 MHz, respectively, which corresponds to gain improvement by 7.6 dBi and bandwidth enhancement of 260 MHz. The proposed antenna is fabricated and tested to compare simulated and measured results. A good compliance is observed between these two results. Equivalent circuit model of the composite structure has been developed and analyzed.