Hallo,
.exe-Dateien sind an sich für Windows, viele laufen aber unter wine, zu beziehen durch die Paketverwaltung. Im Falle des ICQ würde ich beispielsweise Pidgin verwenden, da kannst ein ICQ-Konto anlegen. Als Protokoll ICQ auswählen, deine Zugangsdaten eingeben und schon bist du drin.
Wenn du jetzt noch verraten würdest, welches Linux du verwendest, könnte man dir gezielter helfen, falls noch nötig.