Костел Святого Мартина в стене был построен в конце XII века в поселении Уезд. При сооружении Староместских укреплений в середине XIII в. Уезд был разделен на две части. Большая часть осталась вне крепостных стен, оказавшись на территории будущего Нового города, а меньшая часть с костелом вошла в недра Старого города. Так как костел стоял на границе, южная стена его прилегала с крепостной стене, отсюда и название — Костел Святого Мартина в стене. По соседству с костелом оказались городские ворота, названные воротами Святого Мартина.
Ряд романских архитектурных деталей первоначального однонефного романского костела сохранились в главном нефе храма.
Готическая перестройка костела осуществилась во время правления Карла IV (1350 г.). Главный неф увеличил свою высоту и был перекрыт сводом, стена на юго-западе приобрела призматический вид, а пространство костела расширилось постройкой квадратного в плане пресвитерия. Последний был перекрыт нервюрным (ребристым) сводом, причем такое решение (типичный впоследствии конструктивно-декоративный элемент святынь пражской готики) оказалось одним из первых в Праге. Ребра свода вырастали из консолей, украшенных масками. Место их пересечения украшает роза и звезда.
Впоследствии костел стал святыней реформаторства и гуситской революции.
Свой нынешний вид костел приобрел после перестройки в поздней готике, завершившейся в 1488 г., когда появились два боковых нефа, также перекрытые ребристыми сводами. Финансировала строительство семья Гольцев из Кветнице. Так называемая Гольцева молельня была соединена деревянным мостиком с их домом, находящимся по соседству. О Гольцах и их родственниках Бенешах напоминают и гербы, неоднократно появляющиеся в интерьере храма.
Костел Святого Мартина в стене горел в 1678 г., после чего верхняя часть башни была перестроена. Портал в стиле барокко появился на северной стороне в 1779 г. Вскоре после этого костел упраздняется, превратившись в склад, жилье и магазины.
В 1904 г. выкупленный городом объект реставрируется под руководством К. Гилберта. Теперь башня с гербом Старого города дополняется псевдоренессансными фронтонами.
После первой мировой войны храм приобретают евангелисты, которые проводят здесь генеральную реконструкцию совместно с археологическими исследованиями.
Возле костела когда-то давно было кладбище, где было погребено и прославленное семейство скульпторов Брокофф, о чем свидетельствует памятная доска в наружной кладке пресвитерия. Несколько подлинных надгробных камней разместились в интерьере костела.
