Catalysts are the driver kits. In the release notes (linked on the Catalyst downloads page) it will indicate your card is supported.
A lot of people here are reporting success with the old 4.12 drivers (from 2004/December). I'm playing fine "for now" on the 5.11 drivers (from 2005/November). If you're playing the game alright, I'd recommend not upgrading your drivers.