The Iron Maiden lineup changed rather a lot over the years. Steve Harris, the bassist, is the main writer and the only one never to be replaced. He is, not coincidentally, always pretty high in the mix, too. Linky.
My vote goes to Frank Zappa. He never had the same members in a band for more than a year. Every tour had a different lineup. He toured every year in bothe the U.S. and Europe. Usually, but not always, the members would change between the U.S. and Europe shows. Hell, sometimes the members would change from show to show!
From re-reading Cosmik Debris The Collected History And Improvisations Of Frank Zappa (Son of Revised Edition), I note that starting with his first band The Soul Giants, in 1964, there were at least 36 different lineups. I say at least because some of the lineups were for specific albums and in some cases, specific songs.
I’d list all the different musicians that have been in his bands over the years but then my hands would fall off so I’m not gonna.
Well, bear in mind that some “bands” aren’t really bands. To use an example… Dire Straits WAS a real band for two albums, after which it became Mark Knopfler and whoever he was surrounding himself with. And Rainbow was Ritchie Blackmore + whoever he hired for an album/tour. Ditto for Whitesnake, which began as a real band but quickly became David Coverdale and whoever he was working with this month.
That said, I suppose King Crimson is a contender.
Guitar: Robert Fripp (the only constant member since 1969)
Bass/vocals: Greg Lake, Gordon Haskell, Boz Burrell, John Wetton
Flute/sax/keyboards: Ian McDonald & Mel Collins
Drums: Michael Giles, Andy McCulloch, Ian Wallace, Bill Bruford, Pat Mastelotto
Oh, and God knows how many people have been in Jethro Tull, with Ian Anderson being the only constant.
Mick Abrahams
Ian Anderson
Barriemore Barlow
Martin Barre
Clive Bunker
John Evan
John Glasscock
Jeffrey Hammond-Hammond
Tony Iommi (yes, the Black Sabbath dude was in Tull for a short time)
Eddie Jobson
David Palmer
Dave Pegg
Tony Williams
And those are just the ones I can think of off the top of my head. Anderson and Barre have been together for 35 years or so, but the bassists, drummers and keyboard guys seem to change every other year.
I was definitely going to say Jethro Tull. Either them or Yes.
Current lineup
Jon Anderson - lead vocals (1968–1979, 1983–present)
Chris Squire - bass/vocals (1968–present)
Steve Howe - guitar/vocals (1970–1980, 1991–1992, 1996–present)
Rick Wakeman - keyboards (1971–1974, 1977–1979, 1991–1992, 1996, 2002–present)
Alan White - drums (1972–present)
Original members
Jon Anderson - lead vocals (1968–1979, 1983–present)
Chris Squire - bass/vocals (1968–present)
Tony Kaye - keyboards (1968–1971, 1983–1995)
Peter Banks - guitar (1968–1970)
Bill Bruford - drums (1968–1972, 1991–1992)
Other members
Patrick Moraz - keyboards (1974–1976)
Geoff Downes - keyboards (1980)
Trevor Horn - vocals (1980)
Trevor Rabin - guitar/vocals (1983–1995)
Billy Sherwood - guitar/vocals/keyboard (1994–1995, 1997–1999)
Igor Khoroshev - keyboards (1998–2000)
Napalm Death may not have the sheer number of lineup changes as some older bands, but I think they’re very close to hitting their third generation: not only are no original members left, but I don’t think there’s anyone left who was in the band with an original member.
Fleetwood Mac have some changes, but not nearly as many as previously mentioned bands:
Original lineup:
Peter Green
Mick Fleetwood
John McVie
Jeremy Spencer
Spencer and Green left in 1970.
Christine McVie joined in 1970
From 1970-1974, they went through a few guitarists:
Bob Welch
Bob Weston (note to Bob - wanna stay in the band? don’t screw the boss’ wife)
Danny Kirwan
By 1975, only McVie, McVie, and Fleetwood remained.
Then a couple from Southern California joined: Lindsey Buckingham and Stevie Nicks.
Billy Burnette and Rick Vito joined in 1987. Christine & Stevie stopped touring in 1990. Vito left in 1991. Nicks & Burnette left in 1993 and Bekka Bramlett & Dave Mason joined that year.
In 1997, the 1975 lineup reunited for a successful tour and live album.
Christine McVie left after that tour, effectively retiring (she did release a decent solo project this year).
The most recent tour has the four remaining members from 1975. To me, it ain’t Fleetwood Mac w/o Christine.
I don’t know how close Uriah Heep might be, but I always found it amusing that the back cover of their "Best of " album actually had a chart showing all the members that had come and gone, and when.
Santana. I don’t have the time or patience to look up all of the members, but when Santana was a recording, touring band (and not a star-studded concept, like on the last three albums), they never had the exact same lineup for any two albums. In fact, I think Carlos, the namesake, was the only member to record on more than three of them.
I suppose U2 deserve an honourable mention here: from 1978 {?} to the present, they’ve always had the same line-up {except for once in Sydney when Adan Clayton was too pissed to play}: Bono, The Edge, Larry Mullen, Adam Clayton. That’s what you get for splitting the royalties equally.
Actually, the current Jethro Tull lineup, with Andy Giddings on keys and Jonathan Noyce on bass, has been together since 1995. Doane Perry has been the main Tull drummer since 1984, although there have been occasional substitutes used on a few tours and sessions.