jego matką była Sarah z domu Hawkins, a ojcem pułkownik William Polk, weteran rewolucji amerykańskiej i dobrze prosperujący plantator. William był szkocko-irlandzkiego pochodzenia. Z racji stanowiska naczelnego mierniczego w środkowym Tennessee stał się właścicielem około 100 000 akrów (400 km²) ziemi uprawnejRobins, s. 1537..
Leonidas zapisał się na studia na University of North Carolina at Chapel Hill, ale wkrótce wstąpił do United States Military Academy. Na ostatnim roku stał się niespodziewanie wyznawcą Kościoła episkopalnego, a ochrzcił go w kaplicy Akademii Charles McIlvaine, późniejszy biskup episkopalny Ohio. Polk miał dobre wyniki w nauce i ukończył West Point z 8 lokatą 1 lipca 1827 roku otrzymując stopień brevet-podporucznika artyleriiDupuy, s. 601..
1 grudnia odszedł z wojska i wstąpił do wirginijskiego seminarium duchownego. Został asystentem biskupa Richarda Moore’a w jego kościele w Richmond. Moore wyświęcił Polka w kwietniu 1830 roku na diakona a w rok później na kapłana. 6 maja 1830 roku Polk poślubił Frances Ann Deveraux, córkę Johna i Frances Pollock Devereaux;