Naustremeniai gehörte ehemals zum Deutschen Reich. Im Deutschen Reich hieß der Ort Neu Stremehnen.
Heute heißt der Ort Stremeniai * und gehört zu Litauen.
| historischer Ortsname | Staat | Verwaltung | Zeit |
|---|---|---|---|
| Neu-Stremehnen | Deutsches Reich | Tilsit | vor Versailler Vertrag |
| Naustremeniai | Litauen | Pajėgiai | nach Versailler Vertrag |
| Neu Stremehnen | Deutsches Reich | Heydekrug | 1939 |
| Naustremeniai | Sowjetunion | Pagėgiai/Pagegjaj | 1945 |
| Naustrjamenjaj | Sowjetunion | Pagėgiai/Pagegjaj | 1945 |
| Stremeniai * | Litauen | Šilutė | 1992 |