A high gain microstrip patch antenna with a metamaterial cover over it has been proposed in this paper. A new design namely Criss-Cross metamaterial is being used here. The Criss-Cross unit cell comprises of a cross printed on one face of dielectric substrate and the same cross rotated by 45◦ is being printed on the other face of the same substrate. The DNG behavior, i.e., both ε and µ are simultaneously negative for this metamaterial is obtained at 6 GHz; the patch also operates on the same frequency. The radome cover is constructed by stacking three layers made up of a 3 × 3 Criss-Cross metamaterial array. A 3 × 3 array of Criss-Cross metamaterial unit cell is printed on Duroid substrate. This arrangement of radome cover increases the gain of a simple patch antenna up to 3.66 dB. The radome cover over the antenna is used to protect the structure from environmental hazards. However due to use of conventional dielectric materials as radome, the performance of the antenna degrades. When a metamaterial in printed on such dielectric material, its properties and behavior changes. This leads to improvement of performance of patch antenna along with its physical protection. The directivity of the proposed patch antenna also improves due to the lens behavior of the radome cover over the patch. A conventional radome cover will scatter the EM radiations emitted by the patch antenna. But the metamaterial cover acts as a lens which focuses the EM radiations. This action is once again due to the unusual properties of the metamaterials.