При крепости Св. Александра построили казармы для размещения гарнизона, а с юго-западной стороны поставили церковь. Ее срубили на Олонецкой верфи и доставили на Котлин в разобранном виде. 16 июня 1706 г. ее в присутствии Петра I торжественно освятили во имя Преображения Господня, и «веселились довольно на Котлине острову»[62].
Но одной церкви было недостаточно – по данным А.В. Шелова, в 1708 г. на Котлине насчитывалось служилых 13 681 человек[63]. Поэтому вопрос о второй церкви оказался весьма насущным. Но лишь в 1717 г. на берегу строившегося канала (о канале чуть дальше) построили церковь, которую 13 июня 1718 г. освятили во имя святого апостола Андрея Первозванного. Но место для церкви выбрали неудачно, так как она мешала строительству канала, и ее временно разместили в одном из губернских домов. Андреевский собор, первый каменный в Кронштадте, будет заложен 6 марта 1806 г. При перестройке крепости Св. Александра в 1739 г. решили церковь снести, так как она располагалась на предполагаемом «прикрытом пути»[64], но она простояла до конца XVIII в., а затем, как пишет Шелов, «следы ее исчезли».
Однако далеко не все шло гладко. Вице-адмирал К. Крюйс подчинялся петербургскому обер-коменданту Р.В. Брюсу, которому также подчинялись и сухопутные части. Крюйс тяготился этим подчинением, так как личные отношения с Брюсом у него не сложились. В военных вопросах сухопутные и морские подразделения действовали слаженно, но в мирных постоянно происходили мелкие недоразумения. Например, Крюйс в 1707 г. жаловался на то, что Толбухин взял у него лес на строительство крепости Св. Александра, затем на то, что он не дал рабочим «запасов продовольствия». В следующем году он спрашивал адмирала Апраксина: «Какую команду мне иметь над Кронштадтским комендантом, над полковником Толбухиным, над полуполковником Островским и над их солдатами?». На это Апраксин отвечал: «С генерал-майором Брюсом извольте иметь общее согласие, чтобы не учинилось повреждения интересу Царского Величества; а без него над Котлином, крепостью Св. Александра и Кроншлотом извольте иметь команду». То есть гарнизон на Котлине одновременно подчинялся вице-адмиралу К. Крюйсу и петербургскому обер-коменданту. Такое двоевластие было характерно для Кронштадта на протяжении всей его истории и частенько отрицательно сказывалось на жизни города и крепости.