Took me a while to find out but this is the solution:

1) Install the game, if you run into problems at this stage, set the MafiaLauncher.exe and MafiaSetup.exe executables on CD1 to Compatibility Mode: Windows XP SP2. If it fails, execute it as an administrator.

2) Go into C:\Program Files\Mafia en set the executable Game.exe to Compatibility Mode: Windows XP SP2

3) Go out and search the web for an update to 1.2 (mafia_patch_1.2_eng.exe). On the web you will find sites which refer to patch 1.3 and 1.2, there is no difference. I found it here .

4) Go into C:\Program Files\Mafia en execute Setup.exe. Make sure you configure it as follows:

5) Now sometimes you might be able to play now, if not, follow the next step. You can test this by playing an intro.avi from the c:\program files\mafia folder. If you have video, your good to go!

6) In order to play the intro movies of Mafia (and play the game), you need and Indeo codec. This is unsupported on Vista (as a matter of fact, starting Windows XP SP1 and higher). Go out and fetch a freeware Indeo codec. I’ve got it from this site. Starting from version 5.2 you have to pay for it so make sure you find an older one 🙂

7) Open a command prompt with elevated right (hit the start button, type CMD, right click it and choose  “Run as an administrator”. In the console type: regsvr32 ir50_32.dll

8 ) Try to play the game and please leave a comment if this guide helped you out (or not)!