.GIF's have a 1-bit transparency - a pixel can be not transparent at all (visible), or fully transparent (invisible).
You can still use a transparent background, you just have to watch out when using smoothed edges and select the right background color for them. The rest of the background can stay transparent.