There was only one patent, for LZW, but it was held in multiple countries. It first expired in 2003, and had expired in the last country by 2004.

http://en.wikipedia.org/wiki/Graphics_Interchange_Format#Uni...