Архитектура Николо-Набережной церкви явилась продолжением и развитием традиций муромской архитектуры. В плане - почти квадрат, завершенный на востоке полукружием трехчастной абсиды. Основной объем вытянут по вертикали, двухсветный, перекрытый сомкнутым сводом, на котором покоится пять глухих барабанов с главами луковичной формы, нижняя часть барабанов декорирована циркульными кокошниками.
Фасады украшены деталями из профилированного кирпича. Все четыре угла основного объема подчеркнуты пучком вытянутых по вертикали колонок, из которых угловая большего диаметра. Верхняя часть колонок объединена общей капителью, затем переходящей в раскреповку карниза. Два яруса оконных проемов украшены богатыми тонко нарисованными наличниками, которые в сочетании с сильно развитым по вертикали карнизом, содержащим в своем составе по три декоративных киле-видных кокошника, составляют пышную композицию стены, типичную больше для архитектуры XVII века, чем для архитектуры начала XVIII века, когда эта церковь выстроена.
Одноэтажная трехчастная абсида на углах имеет также колонки. На каждой части абсиды - оконный проем с наличниками, близкими по формам и деталям к наличникам основного объема.
Несмотря на общие черты в композиции со зданиями, выстроенными в Муроме во второй половине XVII века, Николо-Набережная церковь имеет много своеобразных и отличных от XVII века приемов композиции и деталей, отражающих достижения архитектуры этого времени - «петровского барокко».
Вертикально поставленный параллелепипед находится на расширяющемся уступами книзу кирпичном цоколе. На гладкой стене южного фасада в два яруса размещены четыре одинаковых окна. Белокаменные, очень скульптурные обрамления в виде трехчетвертных колонок опираются на резные консоли, соединенные подоконниками в виде тяг. Колонки несут карнизы, над которыми размещаются разорванные фронтоны вогнутого очертания.
Разрывы фронтонов заполнены декоративными вставками. Карниз, состоящий из белокаменных тяг и кирпичных сухариков в виде поставленных под углом друг на друга кирпичей, раскрепован над угловыми колоннами.
В отличие от памятников XVII века вместо закомар или кокошников, которые одновременно были декоративными украшениями сомкнутого свода и выполняли роль кровли этого свода, над карнизом Николо-Набережной церкви продолжается стена, расчлененная тремя декоративными арками с каждой стороны параллелепипеда. В продолжении угловых колонок основного объема сделаны лопатки-пилястры.
Над параллелепипедом возвышается четырехскатная металлическая кровля.
Пять глав с цилиндрическими глухими барабанами, поставленными плотно друг к другу, завершают этот замечательный памятник петровского времени.
Барабаны установлены каждый на подставке, состоящей из четырех полуциркульных кокошников. Верх барабанов завершается карнизом, поверхность декорирована щелевидными нишами.
Купола очень близки к шлемовидной форме и по своим очертаниям в значительной мере отличаются от куполов Благовещенской, Троицкой, Воскресенской и других церквей.
Северный фасад не имеет оконных проемов. Крыльцо с белокаменными ступенями размещено по оси стены.
Окна размещенной в сторону реки трехчастной абсиды имеют украшения, подобные оконным обрамлениям южного фасада. Любопытно отметить, что в нише центрального кокошника с восточной стороны просматривается роспись по кирпичу. Не исключено, что и в других кокошниках могли быть росписи.
Известно, что Николо-Набережная церковь имела несколько этапов строительства.
Пристройка трапезной в 1803 году и вторичное ее расширение в 1847 году вместе с небольшой колокольней закончили композицию замечательного памятника, хотя некоторые детали и поздние пристройки значительно грубее, чем основной памятник. Довольно грубо и безвкусно выполнен вход в церковь с западной стороны.
Трапезная в стиле ампир симметрично примыкает к холодному храму через полуциркульные алтари.
С южной стороны под трапезной имеется подклет с двумя входами. Пять вытянутых по вертикали окон объединены карнизом с арочными тягами над окнами.
Карниз декорирован квадратными нишами. Резной позолоченный иконостас поражает торжественностью и высоким мастерством резчиков-исполнителей.
Безусловный интерес представляет колокольня, расположенная с западной стороны трапезной по оси входа и фактически встроенная в нее. Однако по наличию некоторых деталей четверика колокольни, и в частности, скрытого на чердаке с южной стороны четверика окна, можно предположить, что либо колокольня выстроена в два приема, либо в связи с длительным сроком строительства восьмерик колокольни появился позднее, чем четверик.