Am Ufer der Leega (Lega), wo sie dem langen Großen Oletzkoer oder Treuburger See (jez. Oleckie Wlk.) entspringt, ließ Herzog Albrecht 1559 auf einer Halbinsel eine Jagdhütte errichten, die als Herberge für eine Begegnung mit seinem Vetter Sigismund II., König von Polen, dienen sollte. Nach erfolgreichen Verhandlungen und gemeinsamen Jagdvergnügen beschlossen beide Souveräne – so jedenfalls geht die Sage – zur Erinnerung an dieses Treffen in ihren Ländern jeweils eine Stadt zu gründen. So geschah es und in Polen entstand die Stadt Augustowo, in Preußen Marggrabowa, die Markgrafenstadt. In den Handfesten der Gründungszeit ist von dieser Geschichte aber keine Rede.

Die herzogliche Jagdbude befand sich auf vermutlich prußischem Siedlungsgelände, das Oletzko hieß, wobei allerdings wohl nirgends geschrieben steht, dass der Name Oletzko prußischen Ursprungs ist. Als 1654 anstelle des Jagdhauses ein Schloß als Sitz der Amtshauptmannschaft errichtet wurde, bürgerte sich der Name “Oletzko” bald für die ganze Stadt gleichberechtigt neben dem offiziellen Namen “Marggrabowa” ein, später in gleicher Weise für den Kreis.

Erst am 21. 12. 1928 erhielt die Stadt anstelle von Marggrabowa den Namen “Treuburg” zur Erinnerung an das Ergebnis der in Folge des Versailler Vertrags vom Völkerbund kontrollierten Volksabstimmung 1920 über die Zugehörigkeit der einzelnen Regionen zu Deutschland oder zu Polen. Im ganzen Kreis Oletzko hatten von 28.627 abgegebenen gültigen Stimmen nur 2 Stimmberechtigte für Polen votiert, und das hat damals ganz Deutschland beeindruckt!