This article analyses the conception of the frontier between the territories of the Grand Duchy of Lithuania and the Teutonic Order in the 13th–16th centuries and the evolution of their delimitation processes. The author scrutinizes cases of marking of the ancient land boundaries which witness the origins of the conception of the GDL frontier. When analysing borders between the Order and the GDL in the late 14th century – 1420s, the focus lies on the frontiers and conception of their marking established by the eternal peace treaties of Salynas (1398) and Melno (1422). In addition, the article exhaustively covers the evolution of delimitation processes between the GDL and Livonia and Prussia in 1422 – 16th century. The analysis revealed that the Teutonic Order was establishing a territorial state in the Baltic region, setting the boundaries of territorial units when introducing the administration, thus ex-parte tracing certain landmarks with Lithuania. The boundaries were “chains” of implicit geographic objects, mostly rivers. Some of the latter – the Nemunėlis and the Šventoji – are evidenced in the delimitation of the GDL and the Order of the 15th century. Boundaries of other territories, such as Upytė and Šiauliai, are also found in the records. Such territories were “wedged” between the political organizations of the Order and Lithuania. The first descriptions of state frontier strips were recorder in the cross-border treaties of 1338 signed in Livonia by the GDL ruler Gediminas and Master of the Order. Similar realia are featured in Algirdas and Kęstutis’ treaty with the Livonian Order signed in 1367. Later treaty, entered by the Order and Jogaila and Kęstutis in 1379, describes the “peace strip” and shared territories indicating that the GDL lands stretched from the Nemunas to the west for 6 miles. This was a fragment of the state frontier. By the Treaty of Dubysa of 1382 Jogaila presented the Order with the Samogitian lands up to the river of Dubysa which marked the boundary between the territories. Thus the idea of political borders of the GDL was becoming more and more prominent. Frontier descriptions are for the first time featured in the eternal peace treaties of Salynas (1398) and Melno (1422) signed by the GDL and the Order. Their conception is close to that of the “linear” borders (isolated artificial landmarks, measurements in miles mentioned for the first time in the frontier project of 1420). Sections of the “ancient” borderlines were incorporated into the frontier between the GDL and Livonia. Ruler Vytautas’ delimitations with the Order were a qualitatively new step in the conception of the GDL frontier and marked the birth of the idea of state territory. This is corroborated by the terminology, as in the second half of the 15th century and in the 16th century “Vytautas’ borders” were referred to as “old” and “legitimate”. However, the Treaty of Melno of 1422 did not put a period to the evolution of the GDL frontier. In a number of stripes the frontier stretched along barren lands, therefore in the long run the expansion of internal colonization reached the border and expanded beyond it. Hence, the former territorial decisions were reviewed and revised. The development of the GDL frontier with Prussia in the 15th century was marked by the formation of inhabited borderland, thus resulting in border violation related quarrels. In the 16th century the revision and adjustment of borders continued to be the routine of political life. Sources swarm with documents pertaining to formation of delimitation committees and their activities. Revision of the frontier, especially bilateral, allowed the control of its “movement back and forward” and mitigated disagreements between countries.