Provided are methods of removing perchlorate from water. The methods include contacting water suspected of containing perchlorate with a cationic material. The cationic material includes one or more cationic metal atoms connected by an atom or molecule into an extended structure, and a charge balancing anion. The contacting removes perchlorate (e.g., selectively), if present, from the water. Water treatment vessels, systems and facilities that find use in practicing the methods of the present disclosure are also provided.