Budgeten antogs med en majoritet på endast åtta röster - 153 mot 145.
"Denna budget är en svår uppgift för en regering som vill lämna sitt märke med social rättvisa," premiärminister Alexis Tsipras berättade lagstiftare.
Han gick med på en rad ekonomiska reformer i augusti för att säkra en räddningsaktion för euroområdet på upp till 86 miljarder euro (93 miljarder euro; 62 miljarder pund).
Hans vänsterstyrda regering har varit pressad att ge påtagliga fördelar till de fattigaste medborgarna sedan avtalet.
Budgeten ger 5,7 miljarder euro i nedskärningar i de offentliga utgifterna, inklusive 1,8 miljarder euro i pensioner och 500 miljoner euro i försvar. Den omfattar också skattehöjningar på drygt 2 miljarder euro.
Trots nedskärningarna kommer budgeten fortfarande att ha ett större underskott än 2015 års budget.
Tidigare i år gick Grekland motvilligt med på de stränga villkoren för sin tredje internationella räddningsaktion på fem år.
Efter att ha förlorat sin majoritet i augusti kallade Tsipras till val och återfördes till makten i september med 35 procent av rösterna.
Representanter för euroområdet, Europeiska centralbanken och Internationella valutafonden återvänder i måndags till Grekland för fler samtal om pågående reformer av pensions- och skattesystemen och den offentliga förvaltningen.
Euroområdet har också visat Grekland möjligheten till långsiktig skuldlättnad efter en översyn av framstegen inom ramen för den nya räddningsaktionen.
Den har dock sagt att lättnaden skulle komma i form av längre förseningar innan återbetalningarna börjar eller avslutas, inte en minskning - eller så kallad "hårklippning" - av det belopp som måste återbetalas.
Greklands parlament har snävt godkänt 2016 års budget som inkluderar kraftiga utgiftsnedskärningar och vissa skattehöjningar under den ekonomiska recessionen.