Este de profesie jurist. Din 2002, este avocat. Înainte de a deveni avocat, în 1997, a absolvit Facultatea de Drept a Universităţii „Alexandru Ioan Cuza” din Iaşi, la scurt timp a fost angajat în funcţia de ajutor interimar al procurorului, iar peste un an a devenit ajutor al procurorului de Transport.
A fost procuror până în aprilie 2000, când este numit vicedirector al Air Moldova, companie de stat care, în 2000, este reorganizată. În urma unui contract cu Administraţia de Stat a Aviaţiei Civile, o companie înregistrată în Germania, Unistar Ventures Gmbh, a preluat 49% din AIR Moldova contra sumei de 2,3 milioane USD. Celelalte 51% erau deţinute de Guvern. Compania nou-creată a fost declarată succesoare de drept a Air Moldova. Năstase a lucrat la Air Moldova până în august 2002, când instanţele de judecată au decis desfiinţarea întreprinderii moldo-germane AIR Moldova.
La începutul anului 2015, alături de mai mulți lideri de opinie, jurnaliști, juriști, politologi, ambasadori ș.a. a participat la înființarea Platformei Civice Demnitate și Adevăr. Este unul din liderii mișcăriiprotestatare din Moldova din septembrie 2015 și președintele Consiliului Marii Adunări Naționale (CMAN).
La 1 noiembrie 2015 este ales Președinte al Biroului Executiv al Grupului de Inițiativă constituit în vederea organizării referendumului republican de modificare a Constituției sub aspectul alegerii și demiterii directe a președintelui de către popor, limitarea imunității parlamentare și a numărului de deputați de la 101 la 71. A elaborat proiectele de legi care au fost ulterior expertizate și avizate pozitiv de către Curtea Constituțională.
Andrei Năstase este căsătorit și are trei copii. Este fratele lui VasileNăstase, jurnalist și fost deputat în primul parlament al R. Moldova, semnatar al Declarației de Independență.
Mandatul lui Andrei Năstase la şefia Capitalei este de doar un an, până la alegerile locale ordinare din 2019. Alegerile anticipate din Chişinău au fost provocate de demisia primarului Dorin Chirtoacă. Vizat într-un dosar de corupţie, motiv pentru care a fost suspendat din funcţie la 28 iulie 2017, edilul a decis pe 16 februarie 2018 să-şi depună demisia „în semn de protest şi dezacord faţă de abuzurile care au loc împotriva oraşului”, şi în niciun caz pentru a recunoaşte „acuzaţiile prosteşti” care îi sunt aduse.