U zvaničnoj biografiji stoji da je svoju profesionalnu karijeru započeo u administraciji Osnovne škole "Stojan Novaković“ u Šapcu, a nakon toga postao je načelnik Odeljenja za društvene delatnosti Gradske uprave Šapca. Godinu dana proveo je kao direktor Filijale za Mačvanski okrug Republičkog fonda za zdravstveno osiguranje i koordinator radne grupe za promociju i prevenciju javnog zdravlja u Šapcu.

Politikom počinje da se bavi tokom 1990-tih kao aktivista i član Demokratske stranke (DS), a kasnije i član Glavnog odbora stranke.  Bio je poslanik Narodne skupštine tokom saziva 2012-2014. DS je napustio 2013. godine i pridružio se Poslaničkoj grupi Zajedno za Srbiju koju je formirao Dušan Petrović nakon što je izbačen iz demokratske stranke. Grupa se tokom svog delovanja u Skupštini zalagala za decentralizaciju vlasti i jačanje regionalnih i lokalnih vlasti.

Jednom prilikom Petrović je za Zelenovića izjavio da za dvadeset godina, koliko se bavio politikom, "nikada nije sreo nekoga ko je nalik Nebojši“ i "da ga nisu zamolili da bude na listi za parlamentarne izbore, mislim da nije ni razmišljao o bavljenju politikom“.

U junu 2014. godine Zelenovića je Skupština Grada Šapca izabrala za gradonačelnika. Bio je reizabran 2016. godine kada je postao i predsednik ZSS. Tada je postao poznat i široj javnosti kao jedini gradonačelnik u zemlji koji nije bio naprednjak.

Mnogi su ga videli kao gradonačelnika po "evropskoj meri“. Šabac je bio jedini grad u zemlji koji je vodio politiku energetske efikasnosti,  adekvatno upravljanje otpadom i brigu o zaštiti životne sredine. Zelenović je u Šapcu uveo i model direktnog odlučivanja kako će se trošiti sredstva sakupljena od poreza na imovinu. Preko 100 hiljada punoletnih građana u oko 60 seoskih i gradskih mesnih zajednica glasalo je koji će se projekte finansirati.

Jedan od rezultata takvog upravljanja bilo je izdvajanje čak 7 odsto budžeta Grada za kulturu. "Kultura je naša nasušna potreba, a ne luksuz“, rekao je 2018. godine za "Vreme" Zelenović, objašnjavajući tajne uspeha Šapca.

Vlastima je zasmetao kada je pred Komitetom za monitoring Kongresa lokalnih i regionalnih vlasti "cinkario“ SNS Savetu Evrope zbog pritiska na lokalne vlasti u Srbiji. Govorio je u Strazburu o pritiscima centralne vlasti sa kojima se suočavaju odbornici u onim lokalnim samoupravama u kojima je vladajuća stranka izgubila izbore. "Cilj SNS-a je da, bez izbora, od opozicije postane vlast. Ovo političko nasilje u Srbiji se zove prekomponovanje“.

Nebojša Zelenović bio je jedan od osnivača Saveza za Srbiju, prvog ozbiljnijeg pokušaja ukrupnjavanja opozicionih partija nakon beogradskih izbora 2012. godine. Mada je bio opisivan kao jedan od "najvatrenijih zagovornika bojkota“ izbora 2020. godine, ipak se odlučio da učestvovuje na lokalnim izborima.

Svoju odluku tada je pravdao rečima da je borba za Šabac "borba za normalnu i slobodu Srbiju“. Zbog odluke da izađe na lokalne izbore Zelenović je napustio Savez za Srbiju. Nakon tri puta ponavljanog glasanja zbog izbornih neregularnosti, teških reči, čak i štrajkova glađu članova SNS-a, Zelenović je izgubio vlast u Šapcu.

Neretko je bio na meti provladinih tabloida, a dobijao je pretnje i od ekstremnih desničara poput Miše Vacića.

Smatra da je Srbiji potreban "strateški politički dogovor sa Evropskom unijom i Sjedinjenim Američkim Državama“. "Srbija, koja je fizički okružena članicama EU i NATO, ne može rešiti svoje bezbednosne probleme i postaviti ekonomsku politiku snažnog, brzog, a održivog razvoja bez velikog dogovora za Zapadom“.

Misli da nije moguće imati dobar život bez institucionalno obezbeđene slobode. "Mi kao narod odlučujemo o tome da li će u 21. veku Srbija biti zemlja blagostanja svojih građana ili ćemo se ugasiti zato što nismo sposobni da normalno upravljamo sami sobom“.

Zelenović veruje da je istinskoj opoziciji neophodan razuman dogovor. "Ideološki i programski bliske stranke i organizacije treba, da kao blokovi ili kolone, traže podršku od građana za politiku koju zastupaju“. Ostao je usamljen u ideji organizovanja predizbora po ugledu na mađarsku opoziciju, što bi bio način "da ljudi u Srbiji, koji to žele, ponovo počnu da odlučuju o stvarima u politici“.

Na predstojećim parlamentarnim izborima biće nosilac liste zeleno orijentisanih partija i pokreta okupljenih u koaliciju "Možemo“.

Čitajte dnevne vesti, analize, komentare i intervjue na www.vreme.com