The time the Others were first defeated was during The Long Night. It is said that the Children of the Forest, the First men and possibly a hero called Azor Ahai defeated the Others, and (presumably) some time after, the Wall was built by Brandon the Builder, who supposedly was a Stark.
All of this took place so long ago that no one is really certain of what happened. But as we have seen, the Wall does repel undead (Coldhands could not pass the Wall, ASOS, Sam. Melisandre is impressed with the magic radiating from the Wall, ADWD, Melisandre.) So it is clearly meant as a defence against the Others and their minions.
It is mentioned to be built after the war, as a ward against the Others returning. There is some indication that humans were driven south by the undead legions, which to me implies that they had already been driven past the current location of the Wall. But we really have no clear evidence either way, since this is said to have happened before people even kept historical records (except by carving runes into rocks).