Abstract The existence and construction of perfect maps, also known as de Bruijn arrays or de Bruijn tori, is considered. A c-ary ( r, s; u, v) perfect map is a two-dimensional periodic array with periods rand sand symbols from an alphabet of size cwith the property that every possible u× varray of symbols occurs exactly once in a period of the array. They generalise the well-known de Bruijn sequences. Simple necessary conditions on the parameters r, s, u, vfor the existence of perfect maps are given. These conditions are shown to be sufficient when cis a power of a prime by constructing perfect maps for every allowed parameter set. This result will be applied in the second part to construct further c-ary perfect maps.