Trstenjak was born in the village of Kraljevci near Sveti Jurij ob Ščavnici, in what was then the Austrian Duchy of Styria (now in Slovenia).
He attended the elementary school in his home village and later in Bad Radkersburg (Slovene: Radgona) where he met the philologist Peter Dajnko, with whom he established a close friendship.
After graduating from theology, he was ordained in 1844, then he served as a chaplain in the Lower Styrian villages in Slivnica pri Mariboru (1844–46), Ljutomer (1847), Hajdina (1848), and the town of Ptuj (1849–50).
As a close collaborator of Matija Majar, the author of the program, Trstenjak helped in raising signatures for the establishment of a unified political entity comprising all Slovenian ethnic territory.
After 1849, he established contacts with Janez Bleiweis and Lovro Toman who became the leaders of the Slovene National Movement in the 1850s and early 1860s.