Godkännandet av åtstramningsåtgärden är en viktig seger för president Michel Temer.
Han tillträdde sitt ämbete tidigare i år och lovade att leda landet ur dess värsta recession under många årtionden.
Protester mot åtgärden blev våldsamma i huvudstaden Brasilia och åtminstone ett dussin delstater i landet.
Oppositionen säger att åtgärderna främst kommer att drabba områden som hälsa och utbildning, som redan är underfinansierade.
Tusentals demonstranter tog sig ut på gatorna under senatens session för att protestera mot åtstramningsplanen.
Efter omröstningen kom många demonstrationer in i våld.
I Brasilia satte maskerade demonstranter eld på en buss och marscherade på Globo TV:s lokala kontor, vilket de säger är partiskt mot Temers regering. Men marscherna blockerades av upploppspolisen.
I Sao Paulo attackerades högkvarteret för statens konservativa industriförbund (Fiesp).
För att klara författningstillägget behövde regeringen 49 senatorers röster - tre femtedelar av senaten.
Åtgärden godkändes med en snävare marginal än vad regeringen förväntade sig, med 53-19 röster.
"Vi har vunnit. Det var det viktigaste: att leverera produkten mitt i en storm, "sade regeringsledare i senaten Romero Juca.
Projektet, som i Brasilien kallas PEC 55, fryser utgifterna inom den verkställande, dömande och lagstiftande makten, vilket gör det möjligt för dem att växa endast med inflationstakten n föregående år.
Regeringen hävdar att det är nödvändigt att öka tillväxten och investeringarna och begränsa landets växande offentliga underskott.
Men kritiker säger att de fattigaste i samhället kommer att skadas och att det är orealistiskt att sätta ett utgiftstak för två decennier i förväg, säger BBC:s Julia Carneiro i Rio de Janeiro.
Åtgärden träder i kraft på torsdag.
Den brasilianska senaten har godkänt ett kontroversiellt ändringsförslag till konstitutionen som begränsar de offentliga utgifterna för de kommande 20 åren.