In this paper, a novel miniaturized dual-band embedded near-zero index (NZI) metasurface-based patch antenna is presented. A new methodology based on loading a narrowband microstrip patch antenna (resonating at 4.6 GHz) by a metasurface embedded in the middle of the antenna's substrate is introduced. The loaded antenna has a dual-band resonance of bandwidth of 15% and 43% at 2 GHz and 4.6 GHz, respectively. The metasurface layer is an array of square holes such that there is no hole below the patch. The metasurface layer is designed as a near-zero-refractive-index material (NZRIM). By controlling the phase reflection properties of the structure, the antenna gain is increased by 5.5\,dB, original bandwidth increased ten times and the front-to-back ratio improved from 7 to 187. Also, footprint miniaturization of 56.5% with a maximum size of (1.9λ0)2 is obtained. To the best of the authors' knowledge, such enhancement is the largest to date.