здравствуйте from old fashion здравие (now здоровье - health).
When you say Здравствуйте! you really say = I wish a health to you!
I've been recently learning about relationships between Modern Russian (MR) and Church Slavonic (CS). One of the relationships is город град pairs. This pair здоровье здравие looks like one of these MR - CS pairs.
Interesting!