First-arrival traveltime tomography (FATT) is used to delineate shallow velocity structures to identify static effects in oil exploration as well as to characterize the near surface for geotechnical purposes. Because FATT is generally used for land seismic data processing, it becomes necessary to consider irregular topography especially when performing wave-based tomography. However, the standard Cartesian finite-difference method cannot properly handle irregular topography. Hence, the embedded boundary method (EBM) is incorporated into the frequency-domain damped-wave equation to correctly describe irregular topography. The developed modeling algorithm is used to calculate first-arrival traveltimes and to perform FATT. The EBM-based modeling algorithm accurately describes the irregular surfaces of numerical velocity models on a regular mesh by exploiting the mirror image principle. The accuracy of the EBM-based traveltime calculation is validated by using two homogeneous velocity models with dipping and complex surfaces. The validation results demonstrate that our algorithm is unaffected by the staircase approximation. FATT is then applied to synthetic and real data to demonstrate the applicability of the developed algorithm to velocity models with complex topography. For the real data example, the inverted velocity model is used to apply static corrections. The processing results demonstrate an improvement in the continuity of seismic events, thus confirming the accuracy of the developed FATT method.