2003–2005

Lewis became the ninth coach in Cincinnati Bengals history on January 14, 2003, when he was hired to replace Dick LeBeau, who was fired after the worst season in franchise history in terms of win percentage, edging out Tom Coughlin and Mike Mularkey.^[10] Lewis also had interviews with the Buffalo Bills, the Carolina Panthers, Tampa Bay Buccaneers, and the Cleveland Browns. Lewis also declined head coaching positions in the college ranks with the University of California, Berkeley and Michigan State University to continue pursuing his goal of becoming a head coach in the NFL.^[11]

A contending team in the mid-late 1970s through the 1980s, the Bengals had fallen on hard times in the 1990s and had had several head coaches. However, Lewis didn't take long to return the Bengals to respectability with a nucleus of young players such as quarterback Carson Palmer, running back Rudi Johnson, receivers Chad Johnson and T. J. Houshmandzadeh, and defensive backs Tory James and Deltha O'Neal. After consecutive 8–8 seasons, Lewis led the Bengals to an 11–5 record in 2005, their first winning season, first division title, and first playoff berth in 15 years. However, the Bengals lost in the first round to the eventual Super Bowl XL champion Pittsburgh Steelers with Steelers' Kimo von Oelhoffen being blocked into Carson palmer's leg, forcing Palmer out of the game and requiring reconstructive surgery during the off season.^[12]

2006–2010

The Bengals dropped to 8–8 in 2006, a disappointing season in which they started out 8–5 and then lost their last three games of the season, any one of which could have gotten them into the playoffs with a win. Then they recorded two consecutive losing seasons, including a 4–11–1 record in 2008. But in 2009, Cincinnati recorded their second winning season under Lewis' tenure. This included wins in all six games against their AFC North opponents, marking the first time in franchise history they accomplished this feat.^[13] The Bengals finished the season 10–6, winning the AFC North title and earning only their second trip to the playoffs in 19 years. On January 9, 2010, The Bengals were defeated by the New York Jets 24–14 in the opening round of the playoffs. On January 16, 2010, Lewis was named the Associated Press 2009 NFL coach of the year, after the Bengals improved from a 4–11–1 record in 2008 to a 10–6 regular season record in 2009.

The Bengals slipped to a 4–12 record in 2010, the worst record of Lewis' Bengals coaching tenure and the first time that the team finished last in the AFC North with Lewis as their head coach.

2011–2015

Lewis with the Bengals in 2013

On January 4, 2011, Lewis signed an extension with the Bengals.^[14] The off-season leading up to 2011 was a difficult time for the Bengals. The team lost three of their most productive players from the 2010 season, receivers Terrell Owens and Chad Ochocinco along with defensive back Johnathan Joseph, while quarterback Carson Palmer, the team's starter since 2004, refused to play for the Bengals moving forward, leading to him being traded midway through the season.

However, with the aid of strong play from their first and second-round draft picks, receiver A. J. Green and quarterback Andy Dalton, the Bengals still managed to record their third winning season. Midway through 2011, Lewis won his 65th game with the Bengals, surpassing Sam Wyche as the winningest coach in Bengals history. By the halfway mark, the Bengals' record was 6–2, including a five-game winning streak. It was the first time the Bengals had won five consecutive games since 1988, when the team advanced to the Super Bowl with Wyche as their coach. They finished the season 9–7 and made the playoffs as the #6 seed, where the Bengals lost to the Houston Texans in the wild card round.

On July 31, 2012, the Bengals gave Lewis a two-year contract extension through 2014. Cincinnati started 2012 with a 44–13 loss to the Baltimore Ravens, the most lopsided opening day defeat in franchise history. But the team recovered and won their next three games. After defeating the Steelers in week 16, the Bengals again clinched the #6 seed in the AFC and eliminated the Steelers from playoff contention. This marked the first time the Bengals made the playoffs in consecutive seasons since 1982, ending the longest streak of failure to make consecutive playoff appearances among all 32 NFL teams. Cincinnati finished the season with a 10–6 record, including a franchise record 51 quarterback sacks. However, the season again concluded with a loss in the wild card round handed to them by the Texans.

The 2013 season was one of the most successful in Lewis's career as head coach. Cincinnati finished with an 11–5 record and won their third division title since 2002. They were upset in the first round of the playoffs by the 9–7 San Diego Chargers, a team they had beaten earlier in the season 20–13. It was the third consecutive season that ended in a wild card round playoff loss for Cincinnati.

By 2014, Lewis acquired considerable authority over football operations. Owner Mike Brown was still reckoned as the team's de facto general manager and retains the final say on football matters, but ceded most authority over day-to-day personnel matters to Lewis.^[15]

In 2014, Lewis became the 37th coach in NFL history to record 100 regular season wins. The Bengals continued their playoff streak, posting a 10–5–1 record. They held the fifth seed in the AFC playoffs and drew the 11–5 Indianapolis Colts as their first-round opponent. In week 7, the Bengals had been shut out 27–0 in Indianapolis. They lost again 26–13, despite having 13–10 lead at halftime. With the Bengals' defeat, Lewis tied Jim E. Mora for the most postseason losses as a head coach without a win. There was some speculation that Lewis's head coaching job was on thin ice after a fourth consecutive first-round playoff exit, but on April 22, 2015, Lewis signed an extension with the Bengals through 2016.^[16][17]

Cincinnati started out the 2015 season with an 8–0 record, the best start in franchise history. The team finished the year 12–4, the best record of Lewis' head coaching tenure and marking only the third time the Bengals had ever recorded 12 wins. However, the team was eliminated in a first-round wild card game for the fifth straight year, this time against divisional rival Pittsburgh Steelers. Leading 16–15 near the end of the fourth quarter, Lewis faced criticism for not keeping his players under control after penalties drawn by Vontaze Burfict and Adam Jones moved the Steelers into field goal range and allowed them to make a game-winning kick with eighteen seconds remaining.^[18] The defeat made Lewis the first NFL coach to lose seven postseason games without any wins and the Bengals the first NFL team to lose five straight playoff games in the opening round.

2016–2018

The 2016 and 2017 seasons marked a noted decline for the Bengals, who finished 6-9-1 in the former and 7–9 in the latter to fail to qualify the postseason for two consecutive seasons. The seasons marked Lewis' first losing records with the team since 2010 and first consecutive losing years since 2008, as well as the first losing seasons and missed playoff appearances after the acquisitions of quarterback Andy Dalton and wide receiver A. J. Green.

The losing seasons, combined with Lewis' winless playoff record and previous five consecutive first-round eliminations led to speculation towards his future in Cincinnati and the potential end of his coaching tenure. This speculation was fueled by a report during the 2017 season that said Lewis was planning to leave the Bengals after his contract expired at the end of the season to pursue other opportunities.^[19] Following the conclusion of the 2017 regular season, the report was disproved when Lewis signed a two-year contract extension.^[20] The extension was met with criticism from the media and Bengals fans due to his 0–7 playoff record and only winning 13 out of 32 games in the previous two seasons.^[21][22]

Despite the criticism towards Lewis' return, the Bengals had a strong start in 2018, leading the AFC North with a 4–1 record by Week 5 and holding a 5–3 record before their bye week. After the bye, the team suffered a collapse and lost five consecutive games. During the losing streak, Lewis assumed control of the defense when defensive coordinator Teryl Austin was fired. Afflicted by season-ending injuries to several players and a struggling defense that ranked last in yards allowed, the Bengals finished the year with a 6–10 record to place at the bottom of their division. The season marked the first time since 2008 that the team failed to qualify for the playoffs in three consecutive years and the first time that Lewis had three consecutive seasons with sub-.500 records.

With a year left on his contract, Lewis and the Bengals announced that they had mutually parted ways following the conclusion of the 2018 season on December 31.^[23] Lewis finished as the first Bengals head coach to leave the team with an overall winning record since Bill Johnson in 1978.