Definitely go for cleaning first, may have lot's of gunk built up.

One part of the chain link tool allows you to release the pressure between a link, especially after the chain has been opened and put back together.

I had to replace a chain on a friend's bike because it had been sitting and just the ambient moisture caused rust in the pivot, no amount of anything would free her's up, so I had to replace.