There was no Night's Watch before the White Walkers.
The chronology of the days when the White Walkers first appeared is a bit murky, but we know that the Nights Watch was formed in response to them; Bran also built the Wall specifically to keep them out.
The First Men and the Children of the Forest initially joined forces to fight off The Others, including forming the Night's Watch to keep them at bay. Once the Others had been driven back far enough North, Bran the Builder built the Wall, with the Children's help, and set the Watch to guard it.
It was only later, after the Wall was built, that the Night's King came along. (Also, to be technical, we don't know that he fell in love with an Other, we're making that assumption based on the strong similarities in her description. There's another in-universe theory that she was the daughter of one of the Barrowmen). Eventually, he declared himself king, and was defeated by the Kings south of the Wall. As far as I know, he was never considered a "leader" of The Others (he was working with them in secret, similar to how Crastor was). That information only came out after his death.
I should mention that the leader of the White Walkers is referred to as "the Night King" in the show, that's not the same character as "the Night's King". Both appear to exist in the TV continuity, as Ygritte recites the following story of the Free Folk on one of the DVD extras from the Second Season DVD:
About how one of your king crows found something cold in the woods... with bright blue eyes. How he brought her home, through your wall, and declared himself "Night's King". [...] With the help of the Starks, we killed the demon and cleansed your precious watch.
On the show, the "Night King" is the name given to the first White Walker, who now leads them. In the novels, the Others have only appeared rarely, and there's no mention yet of any command structure, leader, etc.