His father, Aleksa Nenadović, Knez (chief magistrate) of the district of Valjevo, was one of the most popular and respected public men among the Serbs at the beginning of the 19th century.

When the four leaders of the Janissaries of the Sanjak of Smederevo (the so-called Dahias) thought that the only way to prevent a general rising of the Serbs was to intimidate them by murdering all their principal men, Aleksa Nenadović (1749–1804) was one of the first victims.

Prota Mateja became the deputy-commander of the insurgents of the Valjevo district (1804), but did not hold the post for long, as Karađorđe sent him in 1805 on a secret mission to St. Petersburg, and afterwards employed him almost constantly as Serbia's diplomatic envoy to Russia, Austria, Bucharest and Constantinople.

After the fall of Karadjordje (1813), the new leader of the Serbs, Miloš Obrenović, sent Prota Mateja as representative of Serbia to the Congress of Vienna (1814–1815), where he pleaded the Serbian cause indefatigably.

Prota Mateja's memoirs (Memoari Prote Mateje Nenadovića) are the most valuable authority for the history of the first and Second Serbian uprising against the Turks.