A 3D seismic survey (Mallik 3D), covering in the Mackenzie Delta area of Canada’s north, was conducted by industry in 2002. Numerous lakes and marine inundation create a complex near-surface structure in the permafrost terrain. Much of the near subsurface remains frozen but significant melt zones exist particularly from perennially unfrozen water bodies. This results in an irregular distribution of permafrost ice creating a complex pattern of low and high frequency near-surface velocity variations which induce significant traveltime distortions in surface seismic data. A high resolution 3D traveltime tomography study was employed to map the permafrost velocity structure utilizing first-arrival traveltimes picked from 3D seismic shot records. Approximately 900,000 traveltime picks from 3167 shots were used in the inversion. Tomographic inversion of the first-arrival traveltimes resulted in a smooth velocity model for the upper 200 m of the subsurface. Ray coverage in the model is excellent down to 200 m providing effective control for estimating velocities through tomographic inversion. Resolution tests conducted through horizontal and vertical checkerboard tests confirm the robustness of the velocity model in detailing small scale velocity variations. Well velocities were used to validate tomographic velocities. The tomographic velocities do not show systematic correlation with well velocities. The velocity model clearly images the permafrost velocity structure in lateral and vertical directions. It is inferred from the velocity model that the permafrost structure in the near subsurface is discontinuous. Extensions of surface water bodies in depth, characterized by low P-wave velocities, are well imaged by the velocity model. Deep lakes with unfrozen water, inferred from the tomographic velocity model, correlate with areas of strong amplitude blanking and frequency attenuation observed in processed reflection seismic stack sections.