Searching for novel antiferromagnetic materials with large magnetotransport response is highly demanded for constructing future spintronic devices with high stability, fast switching speed, and high density. Here we report a colossal anisotropic magnetoresistance effect in an antiferromagnetic binary compound with layered structure rare-earth dichalcogenide EuTe2. The AMR reaches 40000%, which is 4 orders of magnitude larger than that in conventional antiferromagnetic alloys. Combined magnetization, resistivity, and theoretical analysis reveal that the colossal AMR effect is attributed to a novel mechanism of vector-field tunable band structure, rather than the conventional spin-orbit coupling mechanism. Moreover, it is revealed that the strong hybridization between orbitals of Eu-layer with localized spin and Te-layer with itinerant carriers is extremely important for the large AMR effect. Our results suggest a new direction towards exploring AFM materials with prominent magnetotransport properties, which creates an unprecedented opportunity for AFM spintronics applications.