How can I log in to ICQ using Messages?
Setting Server to login.icq.com and Port to 5190, unchecking SSL in Server Settings tab should help.

Add:

Enter only the first eight characters of your password, leaving off any extras.  This consistently worked for me.  I use OSX 10.9 Mavericks and Messages.

Some have had results leaving the last character off their password.