The Slavic language word deak was used by Hungarians to denote those who studied at schools with textbooks. Pavle Nestorović was among them. The Ottomans captured Nestorović and handed him over to their vassalImre Thököly who put him in prison in Veliki Varadin. He was ransomed in June 1688. In 1688, after the successfulsiege of Belgrade, Nestorović was appointed as commander of Smederevo with the rank of captain. He had under his command 400 Austrian musketeers and 600 Serbs. He was then appointed as commander of the Serbian Militia. Count Đorđe Branković had no military experience and tried to engage Nestorović to command units of Serbs he would mobilize to join the Army of the Holy Roman Empire. Branković may have had the intention to marry Nestorović's sister to establish closer ties with him. Since the beginning of 1689, according to instructions from Vienna, Nestorović organized anti-Ottoman uprisings of Serbs in Sanjak of Smederevo. He was strongly disappointed because the rebels were not immediately supported by the Habsburg imperial army. The rebels left their homes and fieldwork expecting a quick advance by the army; which however continued its invasion into Ottoman Serbia only in July 1689. On 29 August 1689 the Serbian Militia under the command of Dejak as a vanguard unit of the Habsburg army were victorious against a vanguard unit of the Ottoman army during the Battle of Batočina. On 24 September 1689, the Habsburg army captured Niš after defeating the Ottomans at the Battle of Niš. Nestorović and the Serbian unit under his command participated in this battle. When Louis William learned that there were no Ottoman defense positions on Vinik, he ordered Nestorović to attack it. Nestorović managed to bypass the right-wing of the Ottoman forces and with this maneuver won the battle. For this achievement, after this battle Nestorović was promoted to the rank of Lieutenant. On 4 October 1689 Nestorović was appointed as commander of all units of Serbian Militia in Serbia. Following the plan of the supreme command, the army was then split into two parts. One part under command of Louis William headed toward Vidin, while the remaining part of 3,700 soldiers under command of general Piccolomini went from Niš via Prokuplje to Kosovo Vilayet in the middle of October 1689. The major part of his soldiers were 3,400 members of the Serbian Militia under command of Antonije Znorić who was appointed as assistant of Nestorović. In 1695 Nestorović attacked Ottoman-held Temišvar, but without success. In 1697 Nestorović successfully fought against Imre Thököly near Tokaj. In 1699, after the Treaty of Karlovac, the Serb regiment under command of Nestorović was disbanded and he was appointed as Oberstarzt of Titel.
