A joint azimuthal very low frequency–electromagnetic (VLF–EM) and multi-height electromagnetic–terrain conductivity meter (EM–TCM) sounding survey was conducted at a test square area within the 'Tell Hebua' archaeological site at the northwestern Sinai Peninsula. The main objective of the survey was to highlight the applicability and reliability of utilizing such non-invasive surface techniques in a field like archaeological prospection, and hence to image the lateral electrical resistivity structures of the near-surface buried archaeological remains/objects. Consequently, a total of 861 reliable azimuthal VLF–EM and 1701 multi-height EM–TCM soundings were carried out in January 2011 and February 2012, respectively. The data were interpreted extensively and consistently in terms of two-dimensional (2D) transformed EM equivalent current-density and electrical resistivity smoothed-earth models, without using any geological a-priori information. They could be used effectively and inexpensively to image both the buried linear conductive mudbrick walls and small resistive ancient grinding millstones of basic/ultrabasic igneous rocks (or highly-fired, tightly-compacted mudbrick objects) within the fairly-resistive hosting soil. Absolute transformed EM equivalent current-density or resistivity values were not necessarily diagnostic, but their vertical and lateral variations could provide more diagnostic information about the location, shape, size and depth-of-burial of such existing near-surface conductors/resistors, and hence suggested reliable geo-electric earth models. The study demonstrated that a detailed azimuthal VLF–EM multi-height EM–TCM sounding survey can help design an optimal excavation program, not only for the whole 'Tell Hebua' archaeological site, but also for the other historical fortified garrison towns at the northwestern Sinai Peninsula.