Victor Lewis was born May 20, 1950, in Omaha, Nebraska, to Richard Lewis, a saxophonist, and Camille Lewis, a pianist and vocalist, both classically trained musicians who had worked the Midwestern "territory bands" of the 1940s. He grew up hearing Duke Ellington, Count Basie, and Woody Herman at the local theater when their touring big bands passed through Omaha, and he began formal music study at ten and a half, on cello at first because he was still too small for the bass, switching to drums about eighteen months later after watching a Fourth of July drum corps. He also studied classical piano, which is where he learned to read music. By fifteen he was working professionally on Omaha's local scene, called up for jingles, circus dates, and even a taping of the Bob Hope Show, since few of the city's older drummers could read. His playing initially took after the big-band drummers he had grown up watching, but hearing a record of the Miles Davis Quintet with Tony Williams changed his direction, and he began working through Williams, Art Blakey, Kenny Clarke, Max Roach, and Philly Joe Jones. His first job backing a nationally known musician came accompanying saxophonist Hank Crawford on a stop through Omaha.

Lewis moved to Manhattan in 1974. His first New York gig, a night at Boomer's with bassist Buster Williams's group, put him in the room with trumpeter Woody Shaw, who hired him soon after. He made his recording debut a few months later on Shaw's The Moontrane (1975, Muse), and stayed with Shaw's bands through the back half of the decade, appearing on Love Dance (1975), Rosewood (1978, with Joe Henderson), the live Stepping Stones: Live at the Village Vanguard (1978), and For Sure! (1980). Alongside the Shaw association he became a first-call drummer on the era's fusion and pop-jazz dates, recording with Joe Farrell, Earl Klugh, Hubert Laws, Carla Bley, and David Sanborn; it was on Sanborn's records that his writing first reached a wide audience, with Sanborn cutting Lewis's compositions "Seventh Avenue" and "Sophisticated Squaw" (also released as "Agaya") and later "The Legend of the Cheops." In 1977 he recorded Dexter Gordon's Sophisticated Giant (Columbia), a big-band-flavored session arranged by Slide Hampton.

In 1980, Lewis left Shaw's band to join tenor saxophonist Stan Getz, beginning an association that ran until Getz's death in 1991 and produced albums including The Dolphin (1981, Concord, with pianist Lou Levy), Voyage (1986), Anniversary! (1989), and Serenity (1991, with Kenny Barron), plus filmed performances at the Paul Masson and Robert Mondavi vineyard concert series. Getz was the first to record a Lewis original, "I Wanted to Say." Through the same stretch Lewis recorded with vibraphonist Bobby Hutcherson, appearing on Cruisin' the 'Bird (1988, Landmark) alongside tenor saxophonist Ralph Moore, and in 1991 he co-produced, played on, and wrote three tunes for Bobby Watson & Horizon's Post-Motown Bop (Blue Note), one of the more thoroughgoing collaborations of his sideman career. By the end of the 1980s he had become one of jazz's busiest freelance drummers, working with Kenny Barron, Art Farmer, J.J. Johnson, Mike Stern, John Stubblefield, Grover Washington Jr., the Manhattan Jazz Quintet, and Bobby Watson, and he became a mainstay of the Kenny Barron Quintet from its founding, contributing tunes including "Big Girls" (on Barron's Quickstep, Enja) and "Hey, It's Me You're Talkin' To" (on Other Places, Verve/Polygram).

Lewis began recording as a leader in the early 1990s. Family Portrait (1992, AudioQuest) is a suite of pieces dedicated to his own family, with John Stubblefield, pianist Edward Simon, bassist Cecil McBee, percussionist Don Alias, and a six-voice chorus led by Pamela Watson; Lewis himself sings on several tracks and plays a little piano on one. Know It Today, Know It Tomorrow (1993, Red Record) introduced tenor saxophonist Seamus Blake alongside Eddie Henderson, Edward Simon, and Christian McBride, and Eeeyyess! (1997, Enja) documented his touring quintet of Blake, trumpeter Terell Stafford, pianist Stephen Scott, and bassist Ed Howard, with six originals including a Lewis vocal on "Here's To... You Babe." Later leader dates include Grey (2002, with Wolfgang Puschnig and Steve Swallow), Red Stars (2004, Red Record, with J.D. Allen and Fabio Morgera), and a 2019 self-titled Red Record session with Edward Simon, Eddie Henderson, Seamus Blake, Terell Stafford, Christian McBride, and Ed Howard, bringing several longtime collaborators back together. He continued recording into the 2020s, including 2026's Civil Disobedience with Donny McCaslin, Ingrid Jensen, and Bruce Barth.

Lewis has taught throughout his career, giving private instruction, working as a freelance instructor with the New School University Jazz School-Mannes Music School program in New York, and conducting drum clinics internationally; he discovered saxophonist Seamus Blake while teaching at Gunther Schuller's jazz camp in Sandpoint, Idaho. Since 2003 he has been on the faculty of Rutgers University in New Brunswick, New Jersey, teaching drums and coaching jazz combos. Into the 2020s he has continued to lead his own quintet and work steadily as a sideman around New York, including a long-running association with pianist George Cables and frequent appearances at Smalls and Mezzrow with bassist Ed Howard and others.

Lewis's playing is rooted in the post-Tony Williams generation of small-group drummers, built on the same foundation of Art Blakey, Kenny Clarke, Max Roach, and Philly Joe Jones that shaped his contemporaries, but inflected by his own background as a composer and, unusually for a drummer, a working pianist and singer. He is as comfortable driving a hard-swinging small group as he is inside the more textured, fusion-adjacent writing of the David Sanborn and Carla Bley dates of the late 1970s, and his own compositions, several of them recorded by leaders he worked for (Getz, Barron, Sanborn) before he ever led a date himself, mark him as a genuine writer rather than only a time-keeper. His nine years with Getz, spanning the saxophonist's final decade, put him at the center of one of the defining working relationships in that period of Getz's career, and his tenure in Woody Shaw's bands of the mid-to-late 1970s placed him inside one of hard bop's most demanding post-Coltrane trumpet books.