Стрельна, или Стрелина мыза, расположенная на южном берегу Финского залива в 20 километрах от Петербурга по Петергофской дороге, была известна еще в XV веке. В писцовой книге Водской пятины Великого Новгорода 1500 года упоминается речка и деревня «на реке Стрельне у моря». Со старославянского языка название реки переводится как «движение», «течение». Однако уже в XVIII веке родилась легенда, что эта быстрая речка, берущая начало на Ропшинских высотах и впадающая в Финский залив, названа вовсе не по стремительному бегу воды, а в память о «переведении стрелецкого войска Петром I» в 1698 году. Как известно, Петр жестоко расправился с выступлением стрельцов.
В 1703 году, нарезая участки земли вдоль приморской дороги на Петергоф, Стрелину мызу Петр оставил за собой. К 1707 году здесь уже стояли особые «путевые хоромы», где Петр любил останавливаться на отдых во время поездок в Петергоф и Кронштадт.
Тогда же возникла в Стрелиной мызе и первая церковь. По преданию, после своего тайного бракосочетания с Екатериной в Екатерингофской церкви, Петр повелел в память об этом событии перенести церковь в Стрельну и сам будто бы участвовал в ее установке на новом месте. Правда, есть и другое предание, согласно которому первоначальная стрельнинская православная церковь по указанию Петра была переделана из немецкой кирки, издавна здесь стоявшей. От екатерингофской церкви здесь долгое время сохранялся иконостас, иконы, ритуальные сосуды, а также «готический стул с вышитою золотой полосою на спинке», на котором, если верить местным легендам, перед бракосочетанием сидел Петр, ожидая свою невесту.