W dawnej puszczy olitskiej, która znaczną przestrzeń ziemi litewskiej zalegała, na krańcu południowym ówczesnego leśnictwa przełomskiego, nad jednem z licznych jezior teraźniejszą gubernję augustowską oblewających, strudzeni obroną kraju od napadu Krzyżaków, trzej rycerze litewscy założyli osady, w których stare swe lata spokojnie przepędzić zamierzyli.
Trzej rycerze osiedli w takiem miejscu, gdzie las dostarczał potrzebnego do budowy opału i drzewa oraz do pożywienia wszelkiego zwierza, a jezioro i rzeczka w pobliżu płynąca obiecywała mnóstwo ryb rozmaitych i innych właściwych użytków. Takie dogodne miejsce zwróciło uwagę innych wędrowników krajowych, którzy roznosili po kraju wieść o osadzie, nazywając ją Sieniej, to jest starcy. Zaczęli się więc zewsząd ściągać do osady Sieniej krajowcy i na karczunkach leśnych wznosić budowle, które postawione na dwóch wzgórzach nad jeziorem i na trzeciem nad rzeką Sejenką, w ciągu 100 lat, to jest za króla Zygmunta I, już przybrały postać miasta, zwanego w pismach urzędowych z ruska Sieno.
Początki Sejn toną w mrokach dziejów i wiemy o nich niewiele. Mogło być na przyład tak, jak głosi legenda:
Ostatni dzień zimy 1361 r. zbliżał się ku końcowi. Wielki książe litewski, Kiejstut, wracał z dalekiej wyprawy wojennej przeciwko Krzyżakom. I choć po spaleniu Johanisburga i Ekertsbergu dostał się do niewoli i nieomal cudem udało mu się uciec z potężnego zamku w Marienburgu (Malborku), to w sumie wyprawę mógł uznać za udaną. Od litewskich włości dzieliły go już zaledwie dwa dni drogi, a że słońce skryło się już za trójkątne czuby wiekowych świerków, postanowił odpocząć nad rzeką o rzadko spotykanej urodzie. Gdy służba już rozpaliła ognisko, z cienia nadbrzeżnych drzew, podpierając się dębowym kijem wyszedł siwobrody starzec.
- Ktoś ty taki? - zapytał książę.
Starzec dłuższą chwilę milczał, jakby coś sobie z trudem przypominał, aż wreszcie przemówił cichym głosem kalecząc niemiłosiernie litewskie słowa: - "vadinuosi Skirmuntas, mes čia gyvenam keli seniai" (nazywam się Skirmunt, mieszka nas tu kilku starców). Z dalszej rozmowy wynikło, że starzec jest Jaćwingiem ze szczepu Wigranów, co to niegdyś brzegi pięknej rzeki zamieszkiwali.
Książę Kiejstut kilka dni odpoczywał nad puszczańską rzeką, po czym udał się do swojej stolicy - Trok. Po latach przypomniał sobie rzekę, puszczę pełną zwierza i w miejscu, w którym odpoczywał postanowił założyć wieś. Długo głowił się nad tym, jaką tu nazwę nadać wiosce. W pewnej chwili przypomniał sobie dziwne spotkanie z jaćwieskim starcem nazwał je po prostu "seniai", czyli "starcy". A gdy w wiele lat później powstało w tym miejscu miasto, okoliczni Litwini, zniekształcając słowo "seniai" nazwali je "Seinai", czyli po polsku Sejny. Tyle legenda. A jak było naprawdę?
Aleksander Połujański: Wędrówki po guberni augustowskiej w celu naukowym odbyte, 1859