We present a detailed study of the (100) surface of the orthorhombic Al13Co4 crystal using both experimental and ab initio computational methods. This complex metallic alloy is an approximant of the decagonal Al-Ni-Co quasicrystalline phase. After sputter-annealing preparation of the surface at 1073 K, the low-energy electron diffraction pattern recorded exhibits a pseudotenfold symmetry with lattice parameters consistent with those of the bulk model. At this stage, scanning tunneling microscopy (STM) measurements reveal two different types of surface terminations. A comparison between these two surface structures and the bulk planes indicate that the terminations correspond either to an incomplete puckered layer (P) or to an incomplete flat layer (F) . At 1173 K, the majority of the surface consists of P layer terminations. STM images calculated from our proposed surface model are in good agreement with experimental images. X-ray photoelectron diffraction patterns and single scattering cluster calculations further confirm that the local atomic arrangements present in the bulk model are preserved within the near-surface region.