W swoim pierwszym sezonie osiągnął już triple-double notując 22 punkty, 12 zbiórek i 12 asyst w spotkaniu przeciw Los Angeles Clippers.
W następnym roku stał się bohaterem skandalu kiedy wpadł w konflikt z trenerem Donem Nelsonem i nie stawił się na obozie przedsezonowym. Stał się wolnym agentem. Po Webbera zgłosiła się drużyna Washington Bullets. W sezonie 1995/96 zagrał tylko w 15 spotkaniach z powodu urazu ramienia.
W kolejnym sezonie Bullets awansowali do play-offów po raz pierwszy od 9 lat. Był najlepszym punktującym, zbierającym i blokującym drużyny. Po raz pierwszy w karierze wybrany do NBA All-Star Game. W trakcie tego sezonu dwa razy udało mu się zdobyć triple-double – oba przeciwko swojemu byłemu klubowi – Golden State Warriors. 14 maja 1998 został sprzedany do Sacramento Kings.
W nowej drużynie zadebiutował zdobywając 20 punktów i 12 zbiórek przeciw San Antonio Spurs. W swoim pierwszym sezonie gry w Kings był najlepszym zbierającym ligi. W roku 2000 wybrano go do Trzeciej Piątki NBA.