Quote Originally Posted by Super5
Side note: since Kakuzu is so old, I wonder if the symbol on his protector is actually the waterfall village or something else? The waterfall village isn't exactly canon, being as how it only appeared in one of the OVAs and as background in the chuunin exam.
The OVA aside, the appearance of a few gennins from Hidden Waterfall Village in the chuunin exams means that the village is cannon.

Here's my guess:
The land of Waterfall borders the land of Fire, so it's possible that Waterfall was once a more powerful country that lost land to Fire.

The first Hokage founded Konoha, right? I seriously doubt that Fire was a large, powerful country before it had a ninja village. The leaders of Fire probably asked the first Hokage to capture more land from bordering countries. The first Hokage may have invaded Waterfall and fought Kakazu then.

Continuing the speculation, Hidan (who is also seemingly immortal) may come from a fallen country that Konoha or another village completely wiped out.