In this paper we discuss a number of UHF/RFID tag designs including the hybrid loop (Chen and Hsu, International Symposium on Antennas and Propagation, Korea, Vol. 3, 2005, 1045-1048), dual crossed-dipoles, the dual crossed-dipoles utilizing an inductively coupled feed (Choo and Ling, Electron Lett 39 (2003) 3080-3081). We have carried out extensive parametric studies in the process of analyzing the characteristics of the earlier-mentioned antennas, and have investigated several techniques (Choo and Ling, Electron Lett 39 (2003) 3080-3081), including meandering, for size-reduction of these antennas. A design methodology based on the Genetic Algorithm (GA) is presented for the optimization of conformal antennas with Electromagnetic Bandgap (EBG) surfaces (Mittra, Proceedings of International Symposium on Antennas and Propagation 2005 (ISAP2005) Seoul, Korea, 2005, 325-328; Sievenpiper et al., IEEE Trans Microwave Theory Tech 47 (1999), 2059-2074) to improve the antenna performance. The EBG characteristic is realized by utilizing a Frequency Selective Surface (FSS) placed above a thin dielectric substrate backed by a metallic ground plane to act as an Artificial Magnetic Conductor (AMC). The antenna is then placed above the EBG surface to create a conformal integrated EBG - antenna. The initial design of the AMC is carried out by synthesizing a surface whose reflectivity is +1, for a normally incident plane wave. However, since the antenna situated above it produces not just a single plane wave but a spectrum of these waves, it becomes necessary to refine the initial design to optimize the performance of the antenna/AMC composite, and techniques for doing this are discussed in the paper. © 2007 Wiley Periodicals, Inc. Microwave Opt Technol Lett 49: 858-867, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI.10.1002/mop.22265