The new-found two-dimensional antiferromagnetic GdTe$_3$ is attractive owing to its highest carrier mobility among all known layered magnetic materials, as well as its potential application for novel magnetic twistronic and spintronic devices. Here, we have used high-resolution angle-resolved photoemission spectroscopy to investigate its Fermi surface topology and low-lying electronic band structure. The Fermi surface is partially gapped by charge density wave below the transition temperature, the residual part reconstructs making GdTe$_3$ metallic. The high carrier mobility can be attributed to the sharp and nearly linear band dispersions near the Fermi energy. We find that the scattering rate of the linear band near the Fermi energy is almost linear within a wide energy range, indicating that GdTe$_3$ is a non-Fermi liquid metal. Our results in this paper provide a fundamental understanding of this layered Van der Waals antiferromagnetic materials to guide future studies on it.