During Alice's first visit to Wonderland, the Fish Footman was responsible for delivering an invitation to the Duchess from the Queen of Hearts for a game of croquet. The Frog Footman received the letter as they both greet each other and got their wigs tangled up. After getting untangled, the Fish Footman left and the Frog Footman sat down and did not bother delivering the letter as he planned to sit for days and days.
The Fish and Frog Footman were planned to appear in American McGee's Alice but never made it to the final release. It was described that the Fish and Frog Footman can be dealt with together, as they are essentially the same character but with slightly different appearance and voice. A remnant of Wonderland's peaceful days, the Fish and Frog Footman wander hopelessly around the Wonderland Woods. The Footman will peacefully follow, but if hurt they will draw small daggers and enlist the aid of Card Guards.
Concept art of the Fish and Frog Footman can be seen in The Art of Alice: Madness Returns and a model of the Frog Footman can be seen in the Extra Content as it states, "His appearance (formal) and intelligence (modest) were not required for this adventure. He's still a good frog." This could mean the Frog Footman was scrapped once again or he ended up as a random character in the background.