He was born in Lenovac, near Zaječar, in the Crna Reka nahija, into the family of Petar (hence he took Petrović as his surname) and Petrinja. He had two younger brothers, Milutin and Miljko. His father was called Sirenjar Petar ("Peter the Cheese Maker") due to his multitude of livestock which he possessed, and the amount of cheese he sold. His father was a very calm person, though Veljko was an unruly kid. In his youth he kept cattle, even becoming čobanbaša ("head herder") among the local herders. The local Turks often visited their house, eating their food, drinking and taking cheese, butter oil, and milk.
Osman Pazvantoğlu's krdžalije (Ottoman brigands), who were deemed rebels by the Sultan, had fought the Imperial troops at Crna Reka, and then continued to attack local Turks loyal to the Sultan, and burned and devastated several villages in the region, including Lenovac. This prompted Veljko, only 15 years old, to leave his parents and brothers for Vidin. There he was hired as a shepherd by a Turk, and after some time he left for Požarevac, where he was hired by the Vojvoda of Požarevac to prepare food. As he had also spent some time there, at Easter time, he danced the kolo with his friends, forgetting to prepare the important dinner for his master. For this, his master chased to beat him, thus Veljko fled, ending up in the hajduk (Serbian brigands) bands of Stanoje Glavaš. In the winter time of 1803, Glavaš had arranged for Veljko to stay at the house of a jatak ("concealer", civil hajduk supporter) in Dubona, in the Smederevo nahija, where he would work as a shepherd. In the same village Veljko met Marija, a widow and relative of Glavaš, and married her, moving to her house. Not long after the wedding, the Slaughter of the Knezes took place (January 1804), in which prominent Serb leaders were executed by the Janissary military junta of the Sanjak of Smederevo (these janissaries, under the leadership of Kučuk Alija, had murdered sanjak-bey Hadži Mustafa Pasha on 15 December 1801 and taken the rule of the sanjak). As a response to the executions, the Serbian population, without a central figure, took measures of self-defence, and spontaneously attacked the jannisaries.
Hearing of Karađorđe's activities, Veljko immediately asked his wife for hajduk wear and weapons, and joined Glavaš' bands. When Karađorđe arrived at Orašac on the Meeting of the Lord, February 2, 1804, and was chosen by the people, Glavaš, Katić, Čarapić, Jakovljević, Vule, and others, to be the "Supreme Leader of the Serb People", Veljko was present in Glavaš' četa (band of fighters). As the Uprising developed, Glavaš lay away his weapon, and Veljko then served the Smederevo Vojvoda Dušan Vulićević (known as "Đuša") fighting the Ottomans. In the fall of 1805, Vojvoda Đuša was killed by the Turks in Smederevo. Karađorđe put Đuša's younger brother Vujica Vulićević in his place. Veljko became one of Vujica's buljukbašica (a commander of a few men).
With Dušan Vulićević he fought to free Beograd (1806), where he excelled in combat. In 1807 he became a buljubaša / буљубаша and is granted permission from the Council to incite rebellion in the areas of Krivi Vir and Crna Reka. In 1809, he, despite being heavily outnumbered, bravely defended Soko Banja from the Turks. His personal bravery was extraordinary and won him extraordinary praise and fame throughout Serbia and the Balkans. In 1810 he was decorated with Russian Golden Cross for his bravery.
He was noted in the battle of Varvarin, where he was wounded in his left arm and became slightly crippled. In 1811 he became Voivoda of the Timocka Krajina and he was sent to Negotin, in Timocka Krajina In 1813, a detachment of Turkish cavalry attacked him at village of Bukovče where Veljko destroyed them. Turks then set forth with much stronger force, so Veljko retreated to Negotin to defend it.
Large battles took place around Negotin in the summer of 1813. The Turks began to lay siege to Negotin with reinforcements from Vlaška (Walachia). In total, 16,000 Turkish soldiers attacked Negotin, which was defended by 3,000 Serbian soldiers. Veljko fortified Negotin, built a moat and towers, and waited for the Turks. The tallest tower in which Veljko resided, was named Baba Finka. In the moats, together with Veljko were his brothers Milutin and Miljko. Also, there were the prominent buljubaše and Dimbaše Hadži-Nikola, Abrašelibalta among many others. The expected aid that Veljko had requested didn't arrive, and ammunition was running low, so Veljko ordered all tin objects in the city melted down for ammunition, and he ordered metal coins to be put into the cannons. One morning after twenty days of heroic defense, he ordered repair around his moat was struck by a cannonball. He died almost immediately. The Battle of Negotin ended in massive Turkish casualties and the successful escape of the Serbian rebels. His brother Milutin buried him at sunset at Negotin's church. After Veljko's death Turks conquered Negotin and soon all Krajina. He is still remembered for his famous words: "Glavu dajem, Krajinu ne dajem". (I'll give my head, but not Krajina)
Just before the Battle of Negotin, his friend, Vuk Karadžić suggested to him that he send his gold, jewels and other valuables to his family, so they wouldn't fall into Turkish hands. But Veljko refused, believing it wouldn't be proper for a great hajduk and war hero to be slain and found penniless. Veljko considered his personal reputation and glory more important than mere gold.
As a popular hero, there existed songs about him even during his lifetime. There exist over 70 lyrical and 10 epic poems about him. Some of the most known songs or epic poems include "Raslo mi je badem drvo" (Расло ми је бадем дрво) and "Bolan mi leži Kara-Mustafa" (Болан ми лежи Кара-Мустафа).
Serbian comic author Živorad Atanacković (1933-1998) created an adventurous comic on the person of Veljko Petrović, with the theme of the First Serbian Uprising (Hajduk Veljko, 1966).
Some Bulgarian historians have portrayed Veljko as a Bulgarian, as part of their national aspirations. According to Georges Castellan his mother was ethnic Bulgarian.
He is included in The 100 most prominent Serbs.