As you suspected, you will need to use an application like WINE. You can also use PlayOnLinux (which is actually based on WINE) which is designed to make it easier to play Windows games. As it happens, GTA IV is listed as a supported game.
You can get instructions on how to download the program from their site here. Simply select your distribution (either of the Debian or Ubuntu methods should work for you). Once you get the program downloaded you need to get your games installed. There is a visual guide they provide here. From what I can tell, in order to run a steam copy of a game you need the windows version of steam installed, which also appears to be installable from within PlayOnLinux according to this page.
I wish I could give you some personal experience here but I dual-boot so I haven't needed PlayOnLinux, but it looks like it should do the trick given they list GTA 4 as a supported piece of software.