Osnovo nove stavbe tvorijo ruševine poznoromanske cerkve sv. Columbe, ki je bila nekoč središče največje srednjeveške župnije Köln. Leta 1945 je bil uničen med zračnim napadom skoraj do tal, nedotaknjen je ostal le apnenčev kip Gospe v oltarju templja, za katerega je Gottfried Boehm pozneje leta 1950 zgradil posebno kapelo. Hkrati so ruševine cerkve spremenili v nekakšen spominski trg. V začetku sedemdesetih let so na njegovem ozemlju arheologi odkrili ostanke zgradb iz različnih obdobij obstoja Kölna - staro rimske, zgodnjesrednjeveške, romanske in gotske.
Takšen predmet kulturne in zgodovinske dediščine je sam po sebi nenavadno težko zaznati in ohraniti, ko pa se je muzej kölnske škofije odločil, da bo na njegovem mestu - znotraj in okoli obstoječih ruševin - postavila novo stavbo, v kateri bo razstavljena obsežna zbirka verskih objektov umetnost od pozne antike do danes, so se razmere mnogokrat zapletle. Odločitev o razširitvi muzeja je bila sprejeta že leta 1974, vendar so bile ruševine cerkve sv. Columbe za novo lokacijo izbrane šele v začetku devetdesetih let. Leta 1997 je potekal arhitekturni natečaj, na katerem je zmagal projekt izjemnega švicarskega arhitekta Petra Zumthorja. Žirija je ugotovila izjemno spretnost, s katero je Zumthor lahko združil drobce 2000-letne arhitekturne zgodovine Kölna (od temeljev zgradb starih Rimljanov do kapele "Madonna v ruševinah" Boehma leta 1950) v en sam ansambel., kar je več kot le vsota njegovih delov.
Restavriranje in konzerviranje arhitekturnih ostankov je trajalo več let, sama gradnja Columbusovega muzeja pa se je začela šele leta 2003.
Stavba v načrtu spominja na latinski L in je postavljena pod pravim kotom na ulico. Njene stene, obložene z ravnimi in širokimi svetlo sivimi opekami z debelimi sloji vezne malte, se zaradi fine teksture površine sploh ne zdijo rezultat dela zidarja. Vanj so v tleh vgrajeni ostanki cerkvenega obzidja, nad njimi pa lomljeni odseki "perforacije" in velika pravokotna okna, ki so v nasprotju z monumentalno težo 60 cm debelega zidu. Načrt cerkve vključuje majhno gramozno dvorišče na mesto starega župnijskega pokopališča. Obiskovalec vanj vstopi na poti iz avle do glavne "razstavne dvorane" v prvem nadstropju. Ta "dvorana" je ogromna soba, visoka 12 m, vzdolž katere je cik-cak most postavljen nad temelje starodavnih in srednjeveških zgradb, najdenih kot rezultat arheoloških izkopavanj. Zumthor je tu zelo varčno uporabljal umetno razsvetljavo, zato skoraj vsa svetloba vstopa skozi trakove majhnih lukenj na zunanjih stenah stavbe; od znotraj ta tehnika še poudarja navidezno razbarvanje teh zidov, kar lahko razumemo kot aluzijo na načela gotske svete arhitekture ali sklicevanje na dela mistikov tistega časa. V isti prostor je vpisan oktaeder kapele Boehm, ki pa je dostopen zunaj muzeja.
Na koncu most pripelje obiskovalca do prostorov nekdanje zakristije, spremenjene v majhno dvorišče; obstaja skulptura Richarda Serre "Utopljeni in rešeni".
Nad prvo stopnjo sta še dve nadstropji razstavnih dvoran, skupaj šestnajst. Zasnovani so kot samostoječi bloki - "hiše", med katerimi so položene "ulice" belega teraca; vsaka taka dvorana se od drugih razlikuje po velikosti, načinu in intenzivnosti osvetlitve ter poti pregleda. Razstavljeni eksponati so v njih razstavljeni brez upoštevanja kronologije in brez obrazložitvenih besedil in nalepk. Tako so kustosi muzeja želeli doseči nepristransko dojemanje umetniških del s strani občinstva.
V projektu muzeja kölnske škofije je Zumthor nekoč povezoval kulturne spomenike iz različnih obdobij - tako arhitekturnih, ki se nahajajo in situ, kot tudi vključenih v zbirko muzeja - poudarjen lakoničen formalno-arhitekturni jezik, ki ga je arhitektova pozornost omehčala na posebnosti njegove otipne in vizualne lastnosti; tam ima posebno vlogo razsvetljava, ki skorajda ne zadostuje za popoln pregled eksponatov, vendar daje njihovemu zaznavanju posebno ostrino. Zaradi vsega tega je to delo vsaj navzven podobno verskim stavbam v srednjem veku, dobi gradnje uničene cerkve sv. Columbe, ki mu je dala ime, pa tudi času hegemonije katolištva na ozemlju Nemčije, ki še ni poznala preobratov reformacije. Hkrati pa uporaba tehnik svete arhitekture v stavbi muzeja - celo muzeja verske umetnosti - daje misliti na globoko spremembo sistema prioritet sodobnega človeka, ne le na premik duhovne ideale do bolj "sekularne" slike sveta, pa tudi o določenem "populističnem" vidiku celotne sfere moderne kulture. Vendar ne gre pozabiti, da ista arhitektura srednjeveških katedral na Zahodu ni bila zasnovana za peščico elite, temveč za vse vernike brez izjeme; Morda Zumthor nadaljuje to smer v muzeju Columbus in naslavlja vsakega od nas skozi zasnovo svoje stavbe.
