diff --git a/dlls/wined3d/device.c b/dlls/wined3d/device.c
index 3857ebd..a7a586d 100644
--- a/dlls/wined3d/device.c
+++ b/dlls/wined3d/device.c
@@ -2117,6 +2117,11 @@
         }
     }
 
+    /* Delete the palette conversion shader if it is around */
+    if(This->paletteConversionShader) {
+        GL_EXTCALL(glDeleteProgramsARB(1, &This->paletteConversionShader));
+    }
+
     /* Delete the pbuffer context if there is any */
     if(This->pbufferContext) DestroyContext(This, This->pbufferContext);
 
diff --git a/dlls/wined3d/surface.c b/dlls/wined3d/surface.c
index bbf51c7..fc1b10d 100644
--- a/dlls/wined3d/surface.c
+++ b/dlls/wined3d/surface.c
@@ -1413,7 +1413,7 @@
             /* Use conversion when the paletted texture extension is not available, or when it is available make sure it is used
              * for texturing as it won't work for calls like glDraw-/glReadPixels and further also use conversion in case of color keying.
              */
-            if(!GL_SUPPORT(EXT_PALETTED_TEXTURE) || colorkey_active || (!use_texturing && GL_SUPPORT(EXT_PALETTED_TEXTURE)) ) {
+            if( !(GL_SUPPORT(EXT_PALETTED_TEXTURE) || GL_SUPPORT(ARB_FRAGMENT_PROGRAM))  || colorkey_active || (!use_texturing && GL_SUPPORT(EXT_PALETTED_TEXTURE)) ) {
                 *format = GL_RGBA;
                 *internal = GL_RGBA;
                 *type = GL_UNSIGNED_BYTE;
@@ -1424,6 +1424,12 @@
                     *convert = CONVERT_PALETTED;
                 }
             }
+            else if(GL_SUPPORT(ARB_FRAGMENT_PROGRAM)) {
+                *format = GL_RED;
+                *internal = GL_RGBA;
+                *type = GL_UNSIGNED_BYTE;
+                *target_bpp = 1;
+            }
 
             break;
 
@@ -1969,16 +1975,64 @@
     }
 }
 
+const char *fragment_palette_conversion =
+    "!!ARBfp1.0\n"
+    "TEMP index;\n"
+    "PARAM constants = { 0.996, 0.00195, 0, 0 };\n" /* { 255/256, 0.5/255*255/256, 0, 0 } */
+    "TEX index.x, fragment.texcoord[0], texture[0], 2D;\n" /* store the red-component of the current pixel */
+    "MUL index.x, index.x, constants.x;\n" /* Scale the index by 255/256 */
+    "ADD index.x, index.x, constants.y;\n" /* Add a bias of '0.5' in order to sample in the middle */
+    "TEX result.color, index, texture[1], 1D;\n" /* use the red-component as a index in the palette to get the final color */
+    "END";
+
 /* This function is used in case of 8bit paletted textures to upload the palette.
-   For now it only supports GL_EXT_paletted_texture extension but support for other
-   extensions like ARB_fragment_program and ATI_fragment_shaders will be added as well.
+   It supports GL_EXT_paletted_texture and GL_ARB_fragment_program, support for other
+   extensions like ATI_fragment_shaders is possible.
 */
 static void d3dfmt_p8_upload_palette(IWineD3DSurface *iface, CONVERT_TYPES convert) {
     IWineD3DSurfaceImpl *This = (IWineD3DSurfaceImpl *)iface;
     BYTE table[256][4];
+    IWineD3DDeviceImpl *device = This->resource.wineD3DDevice;
 
     d3dfmt_p8_init_palette(This, table, (convert == CONVERT_PALETTED_CK));
-    GL_EXTCALL(glColorTableEXT(GL_TEXTURE_2D,GL_RGBA,256,GL_RGBA,GL_UNSIGNED_BYTE, table));
+
+    /* Try to use the paletted texture extension */
+    if(GL_SUPPORT(EXT_PALETTED_TEXTURE))
+    {
+        TRACE("Using GL_EXT_PALETTED_TEXTURE for 8-bit paletted texture support\n");
+        GL_EXTCALL(glColorTableEXT(GL_TEXTURE_2D,GL_RGBA,256,GL_RGBA,GL_UNSIGNED_BYTE, table));
+    }
+    else
+    {
+        /* Let a fragment shader do the color conversion by uploading the palette to a 1D texture.
+         * The 8bit pixel data will be used as an index in this palette texture to retrieve the final color. */
+        TRACE("Using fragment shaders for emulating 8-bit paletted texture support\n");
+
+        /* Create the fragment program if we don't have it */
+        if(!device->paletteConversionShader)
+        {
+            glEnable(GL_FRAGMENT_PROGRAM_ARB);
+            GL_EXTCALL(glGenProgramsARB(1, &device->paletteConversionShader));
+            GL_EXTCALL(glBindProgramARB(GL_FRAGMENT_PROGRAM_ARB, device->paletteConversionShader));
+            GL_EXTCALL(glProgramStringARB(GL_FRAGMENT_PROGRAM_ARB, GL_PROGRAM_FORMAT_ASCII_ARB, strlen(fragment_palette_conversion), (const GLbyte *)fragment_palette_conversion));
+            glDisable(GL_FRAGMENT_PROGRAM_ARB);
+        }
+
+        glEnable(GL_FRAGMENT_PROGRAM_ARB);
+        GL_EXTCALL(glBindProgramARB(GL_FRAGMENT_PROGRAM_ARB, device->paletteConversionShader));
+
+        GL_EXTCALL(glActiveTextureARB(GL_TEXTURE1));
+        glEnable(GL_TEXTURE_1D);
+        glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_REPLACE);
+
+        glTexParameteri(GL_TEXTURE_1D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
+        glTexParameteri(GL_TEXTURE_1D, GL_TEXTURE_MAG_FILTER, GL_NEAREST); /* Make sure we have discrete color levels. */
+        glTexParameteri(GL_TEXTURE_1D, GL_TEXTURE_WRAP_S, GL_CLAMP_TO_EDGE);
+        glTexImage1D(GL_TEXTURE_1D, 0, GL_RGBA, 256, 0, GL_RGBA, GL_UNSIGNED_BYTE, table); /* Upload the palette */
+
+        /* Switch back to unit 0 in which the 2D texture will be stored. */
+        GL_EXTCALL(glActiveTextureARB(GL_TEXTURE0));
+    }
 }
 
 static BOOL palette9_changed(IWineD3DSurfaceImpl *This) {
@@ -2150,7 +2204,7 @@
         d3dfmt_convert_surface(This->resource.allocatedMemory, mem, pitch, width, height, outpitch, convert, This);
 
         This->Flags |= SFLAG_CONVERTED;
-    } else if (This->resource.format == WINED3DFMT_P8 && GL_SUPPORT(EXT_PALETTED_TEXTURE)) {
+    } else if( (This->resource.format == WINED3DFMT_P8) && (GL_SUPPORT(EXT_PALETTED_TEXTURE) || GL_SUPPORT(ARB_FRAGMENT_PROGRAM)) ) {
         d3dfmt_p8_upload_palette(iface, convert);
         This->Flags &= ~SFLAG_CONVERTED;
         mem = This->resource.allocatedMemory;
diff --git a/dlls/wined3d/wined3d_private.h b/dlls/wined3d/wined3d_private.h
index 431160d..446f2a9 100644
--- a/dlls/wined3d/wined3d_private.h
+++ b/dlls/wined3d/wined3d_private.h
@@ -699,6 +699,7 @@
     /* palettes texture management */
     PALETTEENTRY            palettes[MAX_PALETTES][256];
     UINT                    currentPalette;
+    UINT                    paletteConversionShader;
 
     /* For rendering to a texture using glCopyTexImage */
     BOOL                    render_offscreen;