Microstrip patch antennas mounted over a high impedance EBG substrate within and outside its main bandgap are studied The structure is equivalent to a new microstrip antenna, where the conducting ground plane is replaced by a high impedance EBG layer. Initially, the bandgaps of the dielectric covered EBG structure are determined. Then, patch antennas are placed over the dielectric cover and designed to work within and outside the EBG's main bandgap. Parametric studies are conducted to maximize their impedance bandwidths and gains. It is found that, very wide bandwidths of around 25 percent, can be obtained by variation of the original antenna and EBG parameters. Their gains are similarly increased. The performance of patch antenna on a single layer dielectric substrate, but surrounded by EBG patches, is also investigated Its gain could be increased significantly, but the bandwidth remained small, similar to a corresponding conventional patch antenna