Основата на новата сграда е формирана от руините на късно романската църква Св. Колумба, едно време център на най-голямата енория на средновековния Кьолн. През 1945 г. той е бил унищожен по време на въздушен набег почти до земята, само варовиковата статуя на Дева Мария в олтара на храма е останала непокътната, за което по-късно Готфрид Бем построява специален параклис през 1950 година. По същото време руините на църквата са превърнати в своеобразен мемориален площад. В началото на 70-те години на нейна територия археолозите откриват останките от сгради от различни епохи на съществуването на Кьолн - древноримска, ранносредновековна, романска и готическа.
Такъв обект на културно-историческо наследство сам по себе си е необичайно труден за възприемане и запазване, но когато Музеят на Кьолнската епархия реши да построи на негово място - вътре и около съществуващите руини - нова сграда, която да покаже обширната си колекция от религиозни изкуство от късната античност до наши дни, ситуацията се е усложнила в пъти. Решението за разширяване на музея е взето през 1974 г., но руините на църквата "Св. Колумба" са избрани за новото й място едва в началото на 90-те години. През 1997 г. се проведе архитектурно състезание, в което спечели проектът на изключителния швейцарски архитект Петер Цумтор. Журито отбеляза забележителното умение, с което Цумтор успя да комбинира фрагменти от 2000-годишната архитектурна история на Кьолн (от основите на сгради на древните римляни до параклиса „Мадона в руините“на Бом през 1950 г.) в един ансамбъл, което е повече от просто сбор от частите му.
Реставрацията и консервацията на архитектурните останки отне няколко години, а самото изграждане на музея на Колумб започна едва през 2003 година.
Сградата наподобява латинския L в план и е разположена под прав ъгъл спрямо улицата. Стените му, облицовани с плоски и широки светлосиви тухли с дебели слоеве свързващ разтвор, изобщо не изглеждат, благодарение на фината текстура на повърхността, резултат от работата на зидар. Останки от църковните стени са вградени в тях на нивото на земята, а над тях са счупени участъци от „перфорация" и големи правоъгълни прозорци, контрастиращи с монументалната тежест на 60-сантиметровата стена. Планът на църквата включва малък чакълен двор на място на старото енорийско гробище. Посетителят влиза в него по пътя от фоайето до основната „изложбена зала“на първия етаж. Тази "зала" е огромна стая с височина 12 м, по която зигзаг мост е положен върху основите на древни и средновековни сгради, открити в резултат на археологически разкопки. Зумтор използва изкуствено осветление много пестеливо тук, така че почти цялата светлина навлиза през ивици малки дупки във външните стени на сградата; отвътре тази техника допълнително подчертава привидното обезличаване на тези стени, което може да се разглежда като намек за принципите на готическата свещена архитектура или препратка към произведенията на мистиците от онова време. Октаедърът на параклиса Boehm е изписан в същото пространство, което обаче може да бъде достъпно извън музея.
Накрая мост води посетителя до помещенията на бившата ризница, превърната в малък двор; има скулптура на Ричард Сера „Потънал и спасен“.
Над първото ниво има още два етажа на изложбени зали, общо шестнадесет. Те са проектирани като свободно стоящи блокове - "къщи", между които са положени "улици" от бяло терацо; всяка такава зала се различава от останалите по размер, метод и интензивност на осветяване и път на инспекция. Експонатите се показват в тях, без да се спазва хронологията и без обяснителни текстове и етикети. По този начин кураторите на музея искаха да постигнат безпристрастно възприемане на произведения на изкуството от публиката.
В проекта на музея на Кьолнската епархия Цумтор е обединявал паметници на културата от различни епохи - както архитектурни, разположени in situ, така и включени в колекцията на музея - подчертан лаконичен формален архитектурен език, смекчен от вниманието на архитекта към спецификата на материал, до неговите тактилни и визуални свойства; специална роля там играе осветлението, което е почти недостатъчно за пълен оглед на експонатите, но придава на тяхното възприятие особена острота. Всичко това прави тази работа, поне външно, подобна на религиозните сгради от Средновековието, епохата на построяването на разрушената църква "Св. Колумба", която му е дала името, както и времето на хегемонията на католицизма на територията на Германия, която още не е знаела сътресенията на Реформацията. В същото време използването на техниките на свещената архитектура в сградата на музей - дори музей на религиозното изкуство - кара човек да се замисли за дълбока промяна в системата на приоритетите на съвременния човек, а не само за изместването на духовни идеали към по-"светска" картина на света, но също така и за определен "популистки" аспект от цялата сфера на съвременната култура. Не трябва обаче да се забравя, че същата архитектура на средновековните катедрали на Запад е проектирана не за шепа от елита, а за всички вярващи без изключение; Може би Зумтор продължава тази линия в музея на Колумб, обръщайки се към всеки от нас чрез дизайна на своята сграда.
