Goals from Michael Tonge and Ashley Ward ended the Baggies' 100% home record as the two sides renewed their rivalry.
The previous meeting in March 2002 was abandoned by referee Eddie Wolstenholme with eight minutes left after the Blades, who had three players sent off, were reduced to six men when Robert Ullathorne was forced off injured.
The Baggies were rewarded the points and ended up being promoted to the Barclaycard Premiership, although their stay proved to be a brief one.
But Tonge's ninth-minute strike and a second from Ward eight minutes before the break gave the Blades their third successive win on their travels.
Rob Hulse, the Baggies' top scorer with eight goals, attempted to add to his tally in the fifth minute, however he could not direct his 25-yard piledriver on target.
The visitors, beaten 1-0 at home by Sunderland before the international break, took the lead in the ninth minute. Stuart McCall and Ward were involved in the build-up which resulted in Tonge curling home from the edge of the box.
West Brom nearly conjured up an immediate answer, but Thomas Gaardsoe saw his header from fit-again Wales international Jason Koumas' corner tipped over the crossbar by Paul Gerrard.
The home side continued to press and Neil Clement failed to find the target with a header. Koumas then saw his 20-yard curler pushed over the bar after he tried to take advantage of a mistake by McCall.
Gerrard was called into action again in the 22nd minutes, denying Sekou Berthe as the home side tried to get back on level terms.
Opposite number Russell Hoult, who had been a virtual spectator since conceding that early goal, finally had a save to made, Tonge's free-kick being comfortably collected.
The Blades doubled their advantage in the 37th minute with a well-worked goal, Ward finishing off a fine move which resulting in Nick Montgomery delivering the killer cross.
Baggies boss Gary Megson threw on Lee Hughes and Danny Dichio at the break in a bid to get back into the game.
The move nearly worked as the latter was denied by a stunning save by Gerrard within minutes of the restart.
Dichio had another opportunity to haul Albion back into the game with 23 minutes remaining, but this time he headed Koumas' inswinging corner over the bar.
Albion struggled to breach a resolute Blades defence, and were restricted to long-range efforts as Neil Warnock's side closed out the victory.