Zahlreiche Spuren weisen darauf hin, dass eine Besiedlung der im östlichen Vorharzgebiet gelegenen Fluren, auf denen Gatersleben heute steht, bereits in grauer Vorzeit erfolgte. Unter den Grabungsfunden sind steinzeitliche Werkzeuge aus Stein und Knochen, Hockergräber, uralte Urnen, Hausgeräte aus Ton mit Schnur- und Bandornamenten, Waffen vom Beginn der Eisenzeit und vieles andere mehr. Unser Ort liegt nahe vor den Toren Quedlinburgs im breit gewordenen Selketal, das früher von mehreren Flussarmen durchströmt wurde, aber bei Gatersleben durch eine Furt den Übergang einer Verbindung zwischen Quedlinburg und Magdeburg möglich machte.
Erwähnt wird Gatersleben erst im Jahre 964 in einer Urkunde, in der geschrieben steht, dass Markgraf Gero dem von ihm gegründeten Kloster Gernrode unter anderen Gütern 3 Hufen in "antiquo Gatersleve" schenkte (1 Hufe sind etwa 10 bis 15 Hektar).