Летописи гласят, что 8 мая 1666 года в присутствии царя был освящен алтарь и водружен крест на Казанском храме. Возможно, что в тот год велось строительство уже каменного храма. Во всяком случае, хотя точная дата окончания строительства неизвестна, его архитектурный стиль относят к 1660–1670-м годам. А в 1771 году прибывшие в Коломенское польские дипломаты отмечали: «В начале церковь каменная с притворами по обе стороны в которых окна, полчетверти аршина ширина, мосты войлоками постланы для тепла и мягкого хождения». Мосты – это переход, соединявший храм с дворцом. Сооружение храма велось одновременно со строительством новых царских палат.

История дворца Алексея Михайловича – яркая страница жизни не только села Коломенского, но и всего государства Российского второй половины XVII столетия. Судьбоносные исторические события, в ряду которых стоит строительство дворца, во многом определили создание предпосылок для дальнейшего становления Российской империи. Пришлись эти события на вторую половину 1660-х годов. Если первые два десятка лет своего правления Алексей Михайлович, как говорится, «разбрасывал камни», то начиная с 1665 года пришло время их «собирать».

В 1666 году в Москве начался Большой Московский собор, низложивший патриарха Никона, в 1667 году был подписан мир в Андрусе, оформивший присоединение к России украинских и белорусских земель, тогда же закончилось строительство первого российского корабля «Орел», для которого и был выткан первый российский триколор, а еще был утвержден Новоторговый устав. Вот в какой оптимистичной обстановке затевался царем новый дворец в Коломенском, одной из важнейших функций которого стала представительская. И по внешнему виду дворца, и по его интерьеру у все большего числа приезжих иностранцев должно было создаваться мнение о России как богатом, большом и сильном государстве.

Еще в 1666 году царь повелел заготавливать древесину в лесах по берегам Оки, Угры и Жиздры. Лесами, как мы помним, Россия всегда была богата. Дворец строился не на один год, а потому и отношение к заготовке требовалось особое. Еще в те времена строители знали, в какое именно время надо рубить деревья, как хранить, чтобы лес служил долго и прочно. Дата закладки дворца известна – 3 мая 1667 года (большой церковный праздник!). Царь по такому случаю заранее приехал в Коломенское: «В четверток, после столового кушания, за два часа до вечера государь пошел с Москвы в Коломенское для складывания своих государевых хором». Создавался дворец по заранее одобренному царем проекту, для пущей наглядности и ясности ему была продемонстрирована уменьшенная копия будущих хором.