Кивеннапа - одно из самых древнейших поселений на Карельском перешейке.  Первое упоминание о русских и карельских поселениях к северу от Невы встречается в русских летописях в IX – XI веках.  
В средневековье вся территория Карелии была поделена на погосты (центры). Всю западную часть Карельского перешейка занимал погост Эврепя. Центр погоста находился предположительно между Раковыми озёрами и Вуоксой (район реки Салменкайте — Булатной). Во времена шведского владычества погост из православного становится католическим. С XV века центром католицизма становится Выборг. В городе начинают строить католические храмы. Следом появляются церкви и новые приходы в других местах.
Церковь Святого Креста находилась на месте современного Стрельцова (Муолаа). В дальнейшем приход стал именоваться приходом Святого Креста. Здесь, до 1940 года находились священные камни. На них, по легенде, шведские епископы крестили язычников, обращая их в христианскую веру.
В XV веке из этого большого прихода выделяются два самостоятельных, один из которых — Кивеннапа. О происхождении этого названия выдвигается несколько версий. Наиболее вероятны две. В XV веке на холме Линна-мяки, недалеко от пограничной реки Сестры (Систербек), была возведена шведская крепость Кивенебб — «передовые укрепления». По второй версии название произошло от слияния финских слов «киви» (камень) и «напа» (пуп) и может быть истолковано как «каменный центр», «пуп».