Gmina Lelkowo is a rural gmina (administrative district) in Braniewo County, Warmian-Masurian Voivodeship, in northern Poland, on the border with Russia. Its seat is the village of Lelkowo, which lies approximately 27 kilometres (17 mi) east of Braniewo and 64 km (40 mi) north of the regional capital Olsztyn.
The gmina covers an area of 197.96 square kilometres (76.4 sq mi), and as of 2006 its total population is 3,066.
Gmina Lelkowo contains the villages and settlements of Bartki, Bieńkowo, Dębowiec, Giedawy, Głębock, Grabowiec, Jachowo, Jarzeń, Jarzeński Młyn, Kildajny, Krzekoty, Kwiatkowo, Lelkowo, Lutkowo, Mędrzyki, Miłaki, Młyniec, Nałaby, Perwilty, Piele, Przebędowo, Słup, Sówki, Szarki, Wilknicki Młyn, Wilknity, Wola Wilknicka, Wołowo, Wyszkowo, Zagaje and Zdrój.
Gmina Lelkowo is bordered by the gminas of Braniewo, Górowo Iławeckie and Pieniężno. It also borders Russia (Kaliningrad Oblast).