Основу новой постройки образуют развалины позднероманской церкви Св. Колумбы, в свое время – центра крупнейшего прихода средневекового Кёльна. В 1945 году она была разрушена в ходе авианалета почти до основания, неповрежденной осталась только известняковая статуя Богоматери в алтаре храма, для которой Готфрид Бём построил позже – в 1950 году – специальную часовню. Тогда же руины церкви были превращены в своего рода мемориальный сквер. В начале 1970-х на его территории археологи обнаружили остатки построек разных эпох существования Кёльна – древнеримской, раннесредневековой, романской и готической.
Подобный объект культурного и исторического наследия сам по себе необыкновенно сложен для восприятия и сохранения, но когда музей кёльнского диоцеза постановил соорудить на его месте – внутри и вокруг существующих руин – новое здание для экспозиции своей обширной коллекции религиозного искусства от поздней античности до наших дней, ситуация многократно усложнилась. Решение о расширении музея было принято еще в 1974 году, но развалины церкви Св. Колумбы были выбраны его новым местоположением только в начале 1990-х. В 1997 был проведен архитектурный конкурс, в котором победил проект выдающегося швейцарского архитектора Петера Цумтора. Жюри отметило замечательное мастерство, с которым Цумтор сумел объединить фрагменты 2000-летней архитектурной истории Кёльна (от фундаментов построек древних римлян до капеллы «Мадонна в развалинах» Бёма 1950 года) в единый ансамбль, представляющий собой нечто большее, чем просто сумму своих частей.
Реставрация и консервация архитектурных остатков заняла несколько лет, и непосредственно строительство музея «Колумба» началось только в 2003 году. 
Здание в плане напоминает латинскую L и развернуто своим прямым углом к улице. Ее стены, выложенные из плоского и широкого светло-серого кирпича с толстыми слоями связующего раствора, совсем не кажутся, благодаря тонкой фактуре поверхности, результатом работы каменщика. В них встроены на уровне земли остатки стен церкви, а выше их разбивают участки «перфорации» и большие прямоугольные окна, контрастирующие с монументальной тяжестью стены толщиной в 60 см. В план церкви вписан небольшой засыпанный гравием двор на месте старого приходского кладбища. В него посетитель попадает по пути из вестибюля в главный «выставочный зал» первого этажа. Этот «зал» - огромное помещение высотой 12 м, по которому проложен зигзагообразный мостик над найденными в результате археологических раскопок фундаментами античных и средневековых построек. Цумтор использовал здесь искусственное освещение очень скупо, поэтому почти весь свет попадает внутрь через полосы маленьких отверстий во внешних стенах здания; изнутри этот прием еще сильнее подчеркивает кажущуюся бесплотность этих стен, что можно рассматривать как аллюзию на принципы готической сакральной архитектуры или отсылку к трудам мистиков того времени. В это же пространство вписан восьмигранник капеллы Бёма, в которую, впрочем, можно попасть и снаружи музея. 
В конце, мостик приводит посетителя в помещение бывшей ризницы, превращенное в маленький дворик; там выставлена скульптура Ричарда Серра «Утонувшие и спасенные». 
Над первым ярусом расположены еще два этажа выставочных залов, в общей сложности шестнадцати. Они решены как отдельно стоящие блоки-«дома», между которыми проложены «улицы» из белого терраццо; каждый такой зал отличается от других размером, способом и интенсивностью освещения и маршрутом осмотра. Экспонаты выставлены в них без соблюдения хронологии и без каких-либо пояснительных текстов и этикеток. Таким образом кураторы музея хотели добиться непредвзятого восприятия произведений искусства зрителями. 
В проекте музея кёльнского диоцеза Цумтор использовал для объединения памятников культуры разных эпох – как архитектурных, находящихся in situ, так и входящих в коллекцию музея – подчеркнуто лаконичный формальный архитектурный язык, смягченный вниманием архитектора к специфике материала, к его тактильным и визуальным свойствам; особую роль там играет освещение, почти недостаточное для полноценного осмотра экспонатов, но придающее их восприятию особую остроту. Все это роднит – хотя бы внешне – эту работу с религиозными постройками Средних веков, эпохи строительства разрушенной церкви Св. Колумбы, давшей ему имя, а также – временем гегемонии католичества на территории Германии, не знавшей еще потрясений Реформации. В то же время, использование приемов сакральной архитектуры в здании музея – даже музея религиозного искусства – заставляет задуматься о глубоком изменении системы приоритетов современного человека, не только о смещении духовных идеалов в сторону более «светской» картины мира, но и об определенном «популистском» аспекте всей сферы современной культуры. Однако не следует забывать, что та же архитектура средневековых соборов Запада была рассчитана не на горстку избранных, но на всех верующих без исключения; возможно, Цумтор продолжает эту линию в музее «Колумба», обращаясь через проект своего здания к каждому из нас.
