Rusting is a chemical reaction, so a chemical change of the original matter.

When Iron (symbol Fe) comes in contact with oxygen (symbol O), the result is a compound called Iron Oxide or rust. Iron Oxide or rust is found all over; both iron and oxygen form compounds quite easily, so they are not readily found alone. (The oxygen you breathe is O₂, not elemental oxygen.)

Rust can come in different forms, because iron normally gives up 2 or 3 electrons when it forms compounds. We call these "oxidation states." When iron gives up 2 electrons, it gets a +2 charge, and when it gives up 3 electrons, it gets a +3 charge. To make a neutral compound it must then bond with some element in the proper ratio so as to remove its "excess" positive charge (or, replace its deficit negative charge.)