Live footage showed demonstrators, some waving Moldovan flags just inside the building's entrance as darkness fell. They were blocked from gaining further access by riot police, RFE/RL reported.
Before and during the vote, hundreds of protesters calling for early elections had faced off with riot police outside the building.
The new cabinet approved by legislators is led by Pavel Filip, 49, a deputy chairman of the ruling Democratic Party who has served as minister of telecommunications in several governments since 2011.
Fifty-seven out of the 101 deputies – more than needed – voted in favor of the new cabinet in an attempt to bring a three-month-old political crisis to an end. After the previous government led by Valeriu Stretlet was ousted in October amid a banking scandal, two attempts to name a new prime minister had failed.
The third try was held amid protests by the pro-Russian opposition Socialists, who attempted to postpone the vote and heckled lawmakers during the parliament session.
Several opposition lawmakers briefly interrupted the proceedings, displaying banners demanding "early elections."
According to opinion polls, snap elections could be won by pro-Russian parties that want to renegotiate Moldova's Association Agreement with the EU and develop stronger ties with Moscow.
While the rally outside parliament was organized by pro-Russia opposition groups, a pro-EU movement also took part, building on similar actions at the end of last week.
Both camps are calling for early elections, saying a new cabinet, based on the same ruling parties, will not break with the corrupt practices of previous governments.
On January 16, thousands of people attended three separate rallies in Chisinau, two organized by pro-Russian political forces, while a third was held by the Dignity and Truth (DA) anticorruption civic group.
The protests came after President Nicolae Timofti on January 15 nominated Filip to be the country's prime minister, after two previous nominees failed to gain the office.
The first was Vlad Plahotniuc – a controversial oligarch with close ties to the ruling Democrat Party. His candidacy was rejected by Timofti.
The second, presidential office staffer Ion Paduraru, withdrew his name shortly after he was nominated by Timofti.
If parliament had not managed to approve a government by January 29, Timofti would have had to dissolve the legislature and call early elections.
Moldova, which lies between Romania and Ukraine, has been effectively rudderless since a no-confidence vote toppled the Stretlet government in October after $1 billion – one-eighth of the country's gross domestic product – disappeared from Moldova's banking system.
Billionaire Plahotniuc, a former legislator, has been a main target of the mass protests against the banking fraud that shook Europe's poorest country.
The delay in appointing a new prime minister and apparent deadlock over potential candidates had prompted the pro-Russia opposition to call for snap elections.
Ahead of the January 20 vote, media controlled by Plahotniuc last week broadcast reports that pro-Moscow opposition leaders and Russian security forces were planning a coup in Moldova.
But businessman Renato Usatii, who heads the pro-Russia Our Party and is also mayor of Balti – Moldova's second-largest city – on January 16 denied the reports, labeling them as "nonsense."