During this period, promotional claymation spots and teases became a popular fixture on the program, in which the four hosts were depicted as animated characters in live-action situations, usually starring real-life NFL players.

Beginning with the 1999 season, comedian Jimmy Kimmel (then the co-host of Comedy Central's The Man Show and Win Ben Stein's Money) began making weekly game predictions and performing comedy skits on the show; the following year, Jillian Barberie (then the weather anchor/co-host of Los Angeles Fox owned-and-operated station KTTV's Good Day L.A.) was added to the program to provide weather forecasts for each week's game sites.

On-location broadcast sites Cris Collinsworth left the program in 2002, when he was promoted to Fox's newly formed "A Team" of NFL game announcers, alongside Joe Buck and Troy Aikman (replacing Pat Summerall and John Madden).

Fox produced several promos featuring Buck, Collinsworth and Aikman dressed as characters from the popular 1980s action series of the same name to promote the network's NFL coverage.

He was replaced by comedian Frank Caliendo – at the time, a cast member on Fox's late night sketch comedy series MADtv – who had previously guest starred during Kimmel's skits (performing his well-known impersonation of John Madden).

Caliendo's prognostication skits began to feature his various spot-on celebrity impersonations, including Madden, Jay Leno, Jim Rome and George W. Bush, as well as show hosts Brown, Bradshaw, Long and Johnson.

James Brown left the program after the 2005 season, in order to return to CBS to host its rival pregame show The NFL Today.

During Weeks 6 through 8, while the show broadcast from Hollywood, Jillian Reynolds (née Barberie) returned as weather anchor for the game-day forecast segments.

For the 2006 NFC Championship Game between the New Orleans Saints and Chicago Bears on January 21, 2007, Joe Buck hosted the pregame show with the Fox NFL Sunday crew on location from Soldier Field.

However, the pre-game show was on-site at Lambeau Field for the 2007 NFC Championship Game between the New York Giants and the Green Bay Packers and at Super Bowl XLII.

A segment of highlights and commentary of the previous day's college football games was also featured, as a gesture to Fox's then recent acquisition of broadcast rights to the Bowl Championship Series (BCS).

On January 23, 2011, Fox NFL Sunday also broadcast an on-location edition at Soldier Field in Chicago for the 2010 NFC Championship Game; the program held its Super Bowl XLV pregame show in Arlington, Texas on February 6, 2011.

Starting with the 2011 NFL season, the show introduced a new feature called "Fox :45", which is usually formatted a sing-along parody of a famous song, or as a comedic sketch.

On August 2, 2012, Frank Caliendo announced on his official Twitter account that he would not return to Fox NFL Sunday as a prognosticator for the 2012 season;[9] comedian and former Saturday Night Live cast member Rob Riggle was eventually named as his replacement.

In the latter instance, he commonly gets attacked by a CGI character from the subject of the advertisement (such as Iron Man, a dragon from the movie Eragon, a T-1000 robot from the Fox drama Terminator: The Sarah Connor Chronicles, and The Burger King, who taunted Cleatus by throwing objects at him).

Games aired on the weekend following New Year's Day typically show Cleatus sitting on a bench holding an ice pack to his head, as if nursing a hangover.

During the MLB postseason in October until the conclusion of the World Series (both of which air on Fox), the character is also seen taking baseballs from a basket and hitting them with a bat towards the background.