Perlojos vardo kilmė neaiški. Galima ją kildinti iš bendrinio žodžio perlojas, bet jo reikšmė neaiški, kadangi tai tik dainos žodis: „… Vaikščiojau takeliais, išklotais perlojais, aplink apsodinta žydinčiais kvietkeliais“ (daina nuo Avilių, LKŽ). Mažai tikėtina versija, kad Perloja kilusi nuo žodžio perlas, kadangi šiose vietovėse nėra minima jokia su perlais susijusi veikla.

Pasakojama legenda, kad anksčiau šioje vietoje buvo miestelis, o jame gyveno kunigaikštis Perlius. Šalia miestelio jis pastatė bažnyčią. Vieną sekmadienį į bažnyčią prisirinko labai daug žmonių. Įpusėjus mišioms, prasivėrė žemė ir bažnyčia nugrimzdo. Vėliau toje vietoje atsirado ežeras. Žmonės tą ežerą pavadino Paperloju, o šalia esantį miesteli Perloja. Seni žmonės pasakoja, kad dažnai, sekmadieniais, girdėdavo varpo dūžius sklindančius iš ežero, ir rasdavo bažnytines relikvijas išplautas ant kranto.

1928–1930 m. Perlojoje pastatyta nauja mūrinė bažnyčia, o 1931 m. liepos 19 d. atidengtas paminklas didžiajam kunigaikščiui Vytautui pagerbti su užrašu; „Vytaute Didysai! Gyvas būsi, kol gyvas nors vienas lietuvis“. Šį paminklą kaip laisvės simbolį po Antrojo pasaulinio karo valdžios atstovai ne kartą mėgino nugriauti, tačiau paminklas išliko, nes perlojiškiai tam trukdė, be to jį statant jo viduje buvo įlieti geležinkelio bėgiai ir daug armatūros.

Pokario metais keliasdešimt asmenų išėjo į miškus ir aktyviai įsijungė į pietų Lietuvos partizanų gretas. „Už Perloją ir visą Lietuvą“ žuvusiems partizanams atminti Perlojoje 1995 m. pastatytas paminklas. Kaip ir visoje Lietuvoje taip ir Perlojoje 1941–1951 m. vyko trėmimai į Sibirą. Tuo laikotarpiu per 7 kartus buvo ištremta apie 27 šeimos. Buvo sunaikinta 18 ištremtųjų sodybų.