V. fon Pletenberga dzimšanas gads nav pilnīgi droši zināms, bet dzimšanas vieta ir meklējama Vestfālē, domājams Meijerihas pilī netālu no Pletenbergas pilsētas (no tās arī cēlies dzimtas uzvārds). Topošā mestra vecāki bija vietējie Vestfāles muižnieki - Bertolds un Gosteke Lape.
Valters fon Pletenbergs Livonijā ieradās, domājams, agrā jaunībā jau 15.gadsimta 60.gados. Valtera uzņemšanu ordenī varēja sekmēt viņa radnieciskie sakari, proti, sākot no 14.gadsimta 80.gadiem ordenī sastopami vairāki Pletenbergi. Viens no ievērojamākjiem šīs dzimtas pārstāvjiem - ordeņa Livonijas landmaršals Gederts Pletenbergs (landmāršala amatā 1450. - 1461.), domājams, bija Valtera tēva brālis.
V. fon Pletenberga pirmās gaitas ordenī attiecina uz Narvas pili (tag. Igaunijā). Daži vēsturnieki pieņem, ka 1469.gadā bez vārda pieminētais Aizkraukles pils saimniecības pārzinis (šenks) Pletenbergs bija topošais mestrs. Tomēr pilnīgi drošas ziņas par Pletenberga darbību konkrētā ordeņa struktūrā attiecināmas uz 15.gadsimta 70.gadu pirmo pusi, kad V. fon Pletenbergs atradies Alūksnes komturijā. Jau 1481.gadā viņš minēts kā nozīmīga ordeņa amatpersona - Rīgas pils finansu un saimniecības pārzinis (šafers). Savukārt, 1482. - 1488.g. Valters fon Pletenbergs bija Rēzeknes fogts ar rezidenci Rēzeknes pilī.
Nozīmīgs pavērsiens Pletenberga karjerā bija 1489.gada maijā, kad viņš Vācu ordeņa Livonijas kapitulā tika ievēlēts par ordeņa Livonijas landmāršalu (karaspēka pavēlnieku un mestra padomnieku) ar rezidenci Siguldas pilī. Šajā amtā Pletenbergs guva panākumus veiksmīgi noslēdzot ordeņa karu ar Rīgas pilsētu. 1491.gada martā izšķirošajā kaujā pie Bukultiem ordeņa karaspēks landmāršala vadībā sakāva rīdzinieku karaspēku. Rezultātā Rīgas pilsēta 1491.gadā bija spiesta parakstīt t.s.Valmieras nolīgumu, kas atjaunoja 1452.gada Salaspils līgumu, t.i. Rīgas arhibīskapa un ordeņa divkāršo kundzību pār Rīgas pilsētu. Valmieras nolīgums paredzēja arī karadarbībā nopostīto Rīgas un Daugavgrīvas piļu uzbūvēšanu, kas bija jāveic pilsētai.…
