Oppositionen sade att det skulle arbeta för att frige fängslade oppositionsledare och ta itu med landets ekonomiska kris.
Marian Maduro har tillkännagett en omblandning av kabinettet men lovat att lägga in sitt veto mot amnestilagen för fängslade politiker.
Valresultatet är det värsta för den socialistiska rörelsen som grundades av den avlidne ledaren Hugo Chavez 1999.
Majoriteten innebär att den demokratiska enhetskoalitionen nu kan göra genomgripande förändringar, bland annat genom att ersätta domare i högsta domstolen och göra ändringar i konstitutionen i väntan på godkännande i en folkomröstning.
Man vill också att en av dess ledare, Leopoldo Lopez, som dömdes till 13 års fängelse för att ha anstiftat våld friges - en anklagelsekritiker säger att det var politiskt motiverat.
Men Maduro sade att han skulle blockera alla amnestilagar.
"Mördarna måste åtalas och betala", sa han i en tv-adress.
Han sade att hans socialistparti skulle hålla en "extraordinär kongress" för att ta reda på vad som gick fel vid valet.
Oppositionen varnade under tiden för hotande livsmedelsbrist för venezuelaner.
"Vi uppmanar regeringen att sluta gråta och börja arbeta," oppositionsledaren Jesus Torrealba sade.
"Vi är bara några veckor från ett mycket allvarligt problem när det gäller mat," tillade han.
Valet sågs allmänt som en folkomröstning om president Maduro, Hugo Chavez handplockade efterträdare, och den styrande PSUV:s socialistiska politik.
Oppositionen anklagade Maduros parti för att vanstyra ekonomin och slösa bort landets oljetillgångar.
Venezuela har drabbats hårt av det fortsatt låga oljepriset, dess viktigaste export. Den har också kontinentens högsta inflationstakt.
José Maria Maduro har skyllt situationen på ett "ekonomiskt krig" som förts av oppositionen.
Oppositionen anklagade också regeringen för att öka auktoritärheten.
Valresultatet ger också starkare kraft åt oppositionen om den vill kalla till en folkomröstning om Joseph Maduros framtid. Detta skulle kunna ske först när hans ordförandeskap når sin halvvägspunkt i april nästa år.
Vissa framstående oppositionspersoner vill dock ge José Marian Maduro möjlighet att ändra sin politik som de bär skulden för landets ekonomiska kris.
"Om Maduro inte förändras måste vi ändra regeringen. Men oppositionens svar på den ekonomiska krisen just nu kan inte vara mer politik," Henrique Capriles - som förlorade till Mr Maduro i 2013 års presidentval - berättade AP.
Nästa presidentval ska hållas i april 2019.
100 % +
inflationsnivå för 2015
-10 % minskning av BNP 2015
-6% prognostiserad nedgång 2016
18,1 % prognostiserad arbetslöshet 2016
Venezuelas valmyndigheter har bekräftat att oppositionen har vunnit en viktig två tredjedelars majoritet, vilket gör det möjligt för den att utmana president Nicolas Maduro.