Melvin Sokoloff was born May 10, 1929, in Buffalo, New York, to Russian-Jewish immigrant parents, Samuel and Mildred Sokoloff. His father worked as a drummer around Buffalo, and the son took up the instrument early and turned professional at fifteen. The apprenticeship that followed was a tour of the postwar big-band circuit: Bernie Burns in 1946, Boyd Raeburn in 1948, Alvino Rey in 1948 and 1949, Ray Anthony in 1949 and 1950 and again in 1953 and 1954, and Tex Beneke from 1950 to 1953. By the time he was twenty-five he had spent a decade doing nothing but playing behind a full horn section, which was the only way anyone learned the job.

In 1954 he took the drum chair in the Stan Kenton Orchestra, and the band changed. Kenton's reputation had been built on weight, volume, and ambition rather than swing, and critics had said so for a decade. Wikipedia's account of Kenton's career puts it flatly: the most swinging band Kenton ever fielded arrived when Lewis joined. The records back it up. Contemporary Concepts, cut in July 1955 with Charlie Mariano and Lennie Niehaus on altos and Carl Fontana on trombone, is a bebop date scored for a large ensemble. Kenton in Hi-Fi, recorded in Hollywood in February 1956, re-cut the 1940s hits with a rhythm section that finally moved them. Cuban Fire!, the Johnny Richards suite recorded in New York in 1956, set Lewis against a full Afro-Cuban percussion battery. He left the band and settled in Los Angeles in 1957.

The West Coast years put him on hundreds of sessions. He cut his first date as a leader, Mel Lewis Sextet, in Hollywood in June 1957 for the short-lived Mode label, with Mariano, Bill Holman, Jack Sheldon, Marty Paich, and Buddy Clark. He played on Holman's own big-band album In a Jazz Orbit (Andex, 1958), worked with Gerald Wilson and pianist Hampton Hawes, and took the drum chair in Terry Gibbs's Dream Band, the Los Angeles rehearsal orchestra recorded live at the Seville in Hollywood over three nights in March 1959. He joined Gerry Mulligan's Concert Jazz Band around 1960, appearing on Gerry Mulligan and the Concert Jazz Band at the Village Vanguard (Verve, 1961), and in 1962 he traveled to the Soviet Union as drummer on Benny Goodman's State Department tour, the first American jazz band to perform there. Days after the band came home, on July 12, 1962, he was at Webster Hall in New York cutting Jazz Mission to Moscow with Zoot Sims, Phil Woods, Bill Crow, and Willie Dennis. He moved to New York permanently in 1963.

There he met Thad Jones, who had spent 1954 to 1963 in the Count Basie Orchestra as trumpeter and writer and was the brother of pianist Hank Jones and drummer Elvin Jones. What began around 1964 as after-hours reading sessions for New York studio players hardened, by the end of 1965 and a run of midnight rehearsals at Phil Ramone's A&R Studios, into the Thad Jones/Mel Lewis Orchestra. Max Gordon booked them into the Village Vanguard for three Mondays in February 1966. They opened Monday, February 7, and Gordon told Lewis he would keep it going until it tapered off. It never did. The band recorded Presenting Thad Jones/Mel Lewis and the Jazz Orchestra (Solid State, 1966) within weeks, then Live at the Village Vanguard from an April 28, 1967 set, Monday Night from October 17, 1968, Central Park North (1969), and Consummation (Blue Note, 1970), the album Richard Cook and Brian Morton later placed in the Penguin Guide's Core Collection. Pepper Adams held the baritone chair from the beginning, and the personnel roll over the next decade reads like a directory of New York's best readers: Snooky Young, Jerome Richardson, Jerry Dodgion, Richard Davis, Roland Hanna, Bob Brookmeyer, Eddie Daniels, Billy Harper, Jimmy Knepper, Jon Faddis, and George Mraz. The band toured the Soviet Union in 1972 and Japan in 1974, carried Dee Dee Bridgewater as its featured vocalist from 1972 to 1974, and won the Grammy for Best Jazz Instrumental Performance, Big Band, awarded in 1979 for Live in Munich.

In January 1979 Jones abruptly left for Copenhagen, and the twelve-year partnership was over. Lewis kept the Monday night and kept the band, which became the Mel Lewis Jazz Orchestra. He put Brookmeyer in charge of a new book, recording Bob Brookmeyer, Composer and Arranger from a February 1980 Vanguard run and Make Me Smile and Other New Works by Bob Brookmeyer from concerts of January 7 to 11, 1982, and he commissioned steadily from Jim McNeely, who followed Brookmeyer as the band's writer. Naturally (Telarc, 1979), one of the first digitally recorded big-band albums, was cut March 20 and 21, 1979. Live in Montreux, a program of Herbie Hancock compositions arranged by Bob Mintzer, followed in 1980, and 20 Years at the Village Vanguard (Atlantic, 1986) marked the anniversary. Five nights at the club, February 11 to 15, 1988, yielded three records: Soft Lights and Hot Music and The Definitive Thad Jones volumes one and two, all on MusicMasters, with Kenny Werner at the piano and Joe Lovano, Dick Oatts, and Gary Smulyan in the reeds. Alongside the band he taught jazz drumming at William Paterson College in New Jersey, co-wrote the instruction book It's Time for the Big Band Drummer with Clem DeRosa, and accumulated fourteen Grammy nominations.

Melanoma was diagnosed in the late 1980s. It appeared first in his arm, then his lungs, then his brain. He played the Vanguard until shortly before the end and passed away in New York City on February 2, 1990, at sixty, a few days before the band was to mark its twenty-fourth anniversary at the club. The orchestra took the name Vanguard Jazz Orchestra and has carried on as the Vanguard's house band ever since. The Monday-night engagement Lewis and Jones started on February 7, 1966 has now run past 2,700 Mondays without a break, and the band still plays two sets there every Monday.

Lewis did the opposite of what big-band drumming was supposed to be. Where the tradition ran through Gene Krupa and Buddy Rich toward volume, display, and the drummer as engine, Lewis brought a small-group conception into a sixteen-piece band and described his own job as "supporting," not "pushing or pulling." The sound came off the cymbals: lightweight, dark, overtone-rich Turkish plates, a 21-inch ride on the right, a 19-inch crash-ride on the left, and a riveted 22-inch swish "knocker" on the far right, played on Gretsch wood shells with calfskin batter heads and later on Slingerlands. He insisted on genuine Turkish manufacture, moving from Zildjian to Istanbul late in his career. Rich, whose approach could not have been further from his, said that Lewis does not sound like anybody else, he sounds like himself. His time behind Stan Kenton is the reason that band is remembered as swinging at all, and his time behind Thad Jones is inseparable from the writing: Jones's dense, harmonically crowded charts needed a drummer who would keep the ensemble buoyant rather than drive it, and Lewis was the reason the arrangements breathed. The band he co-founded has been called the most influential big band since the swing era, and the writers who came up inside it, Bob Brookmeyer, Jim McNeely, Bob Mintzer, and Maria Schneider among them, carried its language into the next generation.