diff --git a/PIL/GifImagePlugin.py b/PIL/GifImagePlugin.py
--- a/PIL/GifImagePlugin.py
+++ b/PIL/GifImagePlugin.py
@@ -252,8 +252,9 @@ def _save(im, fp, filename):
         palette = im.encoderinfo["palette"]
     except KeyError:
         palette = None
-    
-    for s in getheader(imOut, palette, im.encoderinfo):
+
+    header, usedPaletteColors = getheader(imOut, palette, im.encoderinfo)
+    for s in header:
         fp.write(s)
 
     flags = 0
@@ -275,14 +276,28 @@ def _save(im, fp, filename):
     except KeyError:
         pass
     else:
+        transparency = int(transparency)
+        # optimize the block away if transparent color is not used
+        transparentColorExists = True
+        # adjust the transparency index after optimize
+        if usedPaletteColors is not None and len(usedPaletteColors) < 256:
+            for i in range(len(usedPaletteColors)):
+                if usedPaletteColors[i] == transparency:
+                    transparency = i
+                    transparentColorExists = True
+                    break
+                else:
+                    transparentColorExists = False
+        
         # transparency extension block
-        fp.write(b"!" +
-                 o8(249) +              # extension intro
-                 o8(4) +                # length
-                 o8(1) +                # transparency info present
-                 o16(0) +               # duration
-                 o8(int(transparency))  # transparency index
-                 + o8(0))
+        if transparentColorExists:
+            fp.write(b"!" +
+                     o8(249) +              # extension intro
+                     o8(4) +                # length
+                     o8(1) +                # transparency info present
+                     o16(0) +               # duration
+                     o8(transparency)       # transparency index
+                     + o8(0))
 
     # local image header
     fp.write(b"," +
@@ -293,7 +308,6 @@ def _save(im, fp, filename):
              o8(8))                     # bits
 
     imOut.encoderconfig = (8, interlace)
-
     ImageFile._save(imOut, fp, [("gif", (0,0)+im.size, 0, rawmode)])
 
     fp.write(b"\0") # end of image data
@@ -304,6 +318,7 @@ def _save(im, fp, filename):
         fp.flush()
     except: pass
 
+
 def _save_netpbm(im, fp, filename):
 
     #
@@ -329,42 +344,81 @@ def getheader(im, palette=None, info=None):
 
     optimize = info and info.get("optimize", 0)
 
-    s = [
+    # start of header
+    header = [
         b"GIF87a" +             # magic
         o16(im.size[0]) +       # size
-        o16(im.size[1]) +
-        o8(7 + 128) +           # flags: bits + palette
-        o8(0) +                 # background
-        o8(0)                   # reserved/aspect
+        o16(im.size[1])
     ]
 
-    if optimize:
-        # minimize color palette
-        i = 0
-        maxcolor = 0
-        for count in im.histogram():
-            if count:
-                maxcolor = i
-            i = i + 1
+    # if the user adds a palette, use it
+    usedPaletteColors = None
+    
+    if palette is not None and isinstance(palette, bytes):
+        paletteBytes = palette[:768]
     else:
-        maxcolor = 256
-
-    # global palette
-    if im.mode == "P":
-        # colour palette
-        if palette is not None and isinstance(palette, bytes):
-            paletteBytes = palette
+        usedPaletteColors = []
+
+        if optimize:
+            # minimize color palette if wanted
+            i = 0
+            for count in im.histogram():
+                if count:
+                    usedPaletteColors.append(i)
+                i += 1
+
+        countUsedPaletteColors = len(usedPaletteColors)
+
+        # create the global palette
+        if im.mode == "P":
+            # colour palette
+            if countUsedPaletteColors > 0 and countUsedPaletteColors < 256:
+                paletteBytes = b"";
+                # pick only the used colors from the palette
+                for i in usedPaletteColors:
+                    paletteBytes += im.im.getpalette("RGB")[i*3:i*3+3]
+            else :
+                paletteBytes = im.im.getpalette("RGB")[:768]
         else:
-            paletteBytes =im.im.getpalette("RGB")[:maxcolor*3]
-            
-        s.append(paletteBytes)
-
-    else:
-        # greyscale
-        for i in range(maxcolor):
-            s.append(o8(i) * 3)
+            # greyscale
+            if countUsedPaletteColors > 0 and countUsedPaletteColors < 256:
+                paletteBytes = b"";
+                # add only the used grayscales to the palette
+                for i in usedPaletteColors:
+                    paletteBytes += o8(i)*3
+            else :
+                paletteBytes = bytearray([i//3 for i in range(768)])
+
+        # TODO improve this, maybe add numpy support
+        # replace the palette color id of all pixel with the new id
+        if countUsedPaletteColors > 0 and countUsedPaletteColors < 256:
+            imageBytes = bytearray(im.tobytes())
+            for i in range(len(imageBytes)):
+                for newI in range(countUsedPaletteColors):
+                    if imageBytes[i] == usedPaletteColors[newI]:
+                        imageBytes[i] = newI
+                        break
+
+            im.frombytes(bytes(imageBytes))
+
+    # calculate the palette size for the header
+    import math
+    colorTableSize = int(math.ceil(math.log(len(paletteBytes)//3, 2)))-1
+    if colorTableSize < 0: colorTableSize = 0
+    header.append(o8(colorTableSize + 128)) # size of global color table + global color table flag
+    header.append(o8(0) + o8(0)) # background + reserved/aspect
+    # end of screen descriptor header
+
+    # add the missing amount of bytes
+    # the palette has to be 2<<n in size
+    actualTargetSizeDiff = (2<<colorTableSize) - len(paletteBytes)//3
+    if actualTargetSizeDiff > 0:
+        paletteBytes += o8(0) * 3 * actualTargetSizeDiff
+
+    # global color palette
+    header.append(paletteBytes)
+    return header, usedPaletteColors
 
-    return s
 
 def getdata(im, offset = (0, 0), **params):
     """Return a list of strings representing this image.
diff --git a/setup.py b/setup.py
--- a/setup.py
+++ b/setup.py
@@ -285,10 +285,9 @@ class feature:
             elif _find_library_file(self, "tk" + TCL_VERSION):
                 feature.tk = "tk" + TCL_VERSION
 
-        if (
-                _find_include_file(self, "webp/encode.h") and
+        if (_find_include_file(self, "webp/encode.h") and
                 _find_include_file(self, "webp/decode.h")):
-            if _find_library_file(self, "webp"):
+            if _find_library_file(self, "webp"): # in googles precompiled zip it is call "libwebp"
                 feature.webp = "webp"
 
         #

diff --git a/Tests/test_file_gif.py b/Tests/test_file_gif.py
--- a/Tests/test_file_gif.py
+++ b/Tests/test_file_gif.py
@@ -9,7 +9,8 @@
 
 # sample gif stream
 file = "Images/lena.gif"
-data = open(file, "rb").read()
+with open(file, "rb") as f:
+    data = f.read()
 
 def test_sanity():
     im = Image.open(file)
@@ -25,4 +26,4 @@ def test(optimize):
         im.save(file, "GIF", optimize=optimize)
         return len(file.getvalue())
     assert_equal(test(0), 800)
-    assert_equal(test(1), 32)
+    assert_equal(test(1), 38)

Saving gifs with optimize=True results in bad image
As already discovered by other people:
http://mail.python.org/pipermail/image-sig/2011-June/006777.html

![sprite](https://f.cloud.github.com/assets/506283/458525/35c8a04e-b3da-11e2-891f-f810765aa082.gif)

Image was created using:

``` python
image = Image.new('RGB', some_size)

image.paste(img1, ...)
image.paste(img2, ...)
image.paste(img3, ...)

# Save image with optimize=False works fine
image.save('sprite.gif', 'gif', optimize=True)
```


Of course we can use PNG8 instead - which works perfectly.

Thanks, any idea how to fix? If so, please send a pull request.

Optimize tries to reduce the palette size and seems to fail. I've no time to look into this now but I can debug it in a few weeks.

Thanks! No hurry

@saily or anyone else want to look at this? I don't want to over-tax @d-schmidt or @wiredfool 

I think I found the problem.

The optimize code is virtually useless...
