31-åringen har tecknat ett två och ett halvt års kontrakt hos The Hawthorns med en 12-månadersoption.
West Ham var också intresserad av att underteckna Fletcher, men en flytt till Upton Park bröt samman förra helgen.
Albion misslyckades i deadline dag flyttar för att underteckna West Ham strejkaren Carlton Cole och Norwich försvararen Martin Olsson, men behöll Brown Ideye och Graham Dorrans.
Fletcher gjorde 342 framträdanden för United men började bara fem gånger för klubben efter Louis van Gaal tog över som chef på sommaren.
Scot, som återhämtade sig från kronisk tarmsjukdom ulcerös kolit att återuppta sin karriär i december 2013, hade varit på Old Trafford sedan han var skolpojke och hjälpte Red Devils vinna Premier League titeln fem gånger.
Men med hans kontrakt satt att löpa ut i somras fick han en gratis överföring för att hjälpa honom att hitta en ny klubb i detta överföringsfönster.
"Detta är en fantastisk ny utmaning för mig i min karriär," Fletcher berättade West Broms hemsida.
"Jag har tillbringat min karriär på Manchester United och det är allt jag någonsin känt. Men jag kände att det var rätt tillfälle att flytta och jag är inte sentimental över att göra det."
Fletcher är den andra spelaren signerad av West Brom huvudtränare Tony Pulis efter £ 4,75m fånga av ytter Callum McManaman från Wigan.
Scotland kapten kommer att bära nummer 24 skjorta för baggies.
Albion hade hoppats underteckna Cole och Olsson på en hektisk deadline dag, med Dorrans inställd på att gå med Norwich och Ideye kopplade med ett drag till Qatari klubb Al Gharafa.
Men Cole kallades tillbaka till West Ham när de inte signerade Tottenhams Emmanuel Adebayor, och Olsson misslyckades med att anlända till sjukvård i tid.
Ordförande Jeremy Peace sade: "Vi fick inte alla affärer gjorda som vi kunde ha men vi är glada över att få in en spelare och en karaktär av Darrens kaliber.
""Vi blev besvikna för Carlton eftersom han också var glad över att komma med oss men av skäl som låg utanför vår kontroll kunde vi inte slutföra affären. Detsamma kan sägas om förslaget som berör Martin Olsson och Graham.
"Men vi har alltid hävdat att januari är en svår tid att göra affärer och vi är mycket nöjda med de avtal vi har gjort."
West Brom har undertecknat Scotland Midfielder Darren Fletcher på en gratis transfer från Manchester United.