The Night's Watch wasn't always made up of criminals avoiding execution and various people that others wanted exiled.
From https://gameofthrones.fandom.com/wiki/Night%27s_Watch
"The Watch was once highly regarded and their ranks were filled with volunteers from noble houses, as serving was a sign of selfless devotion to the protection of the realm."
The Wall and the Night's Watch were created thousands of years ago after The Long Night, which was the last winter the White Walkers made war on mankind. https://gameofthrones.fandom.com/wiki/Long_Night That particular war was so terrible that the survivors wanted to prepare for the event that the White Walkers returned, and so they made The Wall and the Night's Watch.
At first the memory of the Long Night was fresh, and so people volunteered to serve on the wall. It was also at that time considered an honorable alternative to execution for criminals.
But of course as thousands of years passed, most either thought the White Walkers were gone forever or else never existed in the first place. Those in the noble houses stopped volunteering because they saw no reason they should give up their titles and property to serve, and for criminals it was seen as a cowardly and perhaps miserable way to escape execution. It may even be the case that houses less honorable than Stark often denied criminals the option to serve, because people likely would have seen it as a criminal escaping justice.