Men først i år 1635 starter de rigtige byggeplaner, og i denne forbindelse foreslog hans astronom Christian Longomontanus ham at opføre et astronomisk tårn. Longomontanus (eller Lomborg som var hans danske navn) havde først foreslået Valby Bakke som stedet for et nyt observatorium, men tårnet skulle pynte på den nye kirke og være tæt på universitetet, så observatoriet kom til at ligge inde i byen.

Som bygmester valgtes Hans van Steenwinckel den yngre søn af kongelig bygmester Hans van Steenwinckel den ældre, der i 1578 var blevet indkaldt til arbejdet på Kronborg. Steenwinckel den yngre nåede dog ikke at færdiggøre tårnet, idet han døde i 1639. Fra 1640 var overbygmesteren Leenart Blasius, som kom fra Holland. At kongen vidste besked med hans kvalifikationer fremgår af hans breve:

"Den nye Bygmesters Bestilling skal gøres paa 600 Daler, og omendskiøndt Besoldningen løber højere end den forriges, og han intet kan tegne saa vel, saa kan han dog bedre staa Værket for end som den forrige"

 For at skaffe plads til bygningen var det nødvendigt at fjerne en del huse derfor skrev Christian IV den 17. april 1637 til Rentemesteren (finansministeren):

"Imorgen skal to hundrede Mand af Holmens Folk, Arkeliet (Tøjhuset) og Soldater tage Taget af de Huse og Boder, som findes paa den Plads, som den nye Kirke skal staa, tvært over for Regentzen, og sætte Tagstenene udi den Vinkel, som findes ved Hans Boisens Hus. Naar sligt sket er, da skal Husene nedtages og Tømmeret, stort og smaat, føres op paa Volden, der som Stenene blev ført neder af Volden, hvortil Rustvognene (hærens vogne til udrustning), Slottets Arbejdsheste, item de af Provianthuset og Børnehuset skal bruges, saa at man i en Hast kan faa det op paa Volden, og skal der sættes Vagt allevegne, paa det man kan, saa meget ske kan, hindre Folks Tilløb og Stjælen; der skal ogsaa ordineres Officerer, som giver Agt paa samme Arbejde."

det gav dog anledning til visse problemer:

Til her Corfitz Wlfeld.   

4 Maj 1638.

C. 4. Wor synderlig gunst tilforn. Wider, at efftersom os elskelige Michel Søffrensen, raadmand udj wor kiøbsted Kiøbenhaffn, vnderdanigst for os haffuer ladit andrage, huorledis hand for nogen rum tid siden, der hand vaar hospitals forstandere udj Wartou, skall haffue aff de fattigis penge sammestedtz udsat paa rente hoes en borger der udj forskreffne Kiøbenhaffn ved naffn Claus Lauritzen nogle hundrede daller och till forsichring at skall haffue udj pant tagit aff hannom siuff woninger liggendis i Landemerchet der i forskreffne Kiøbenhaffn, disligeste hans gaard i Kiøbmagger gaden der sammestedtz, huilchet hand beretter till tinge rigtig skall vere giort, och samme hans gaard och woninger nu at vere nederbrutt och paa stedet igien en nye kierche at skall opbyggis, vnderdanigst begierendis hand paa de fattigis wegne maa bliffue contenterit, daa bede wi eder och naadigst wille, at j med flid forfarer, om forskreffne Michell Søffrensens pant udj forskreffne woninger och gaard er saa rigtig, som det sig bør, och dersom det rigtig befindis, j daa tilholder dennom, som er befalit at annamme de penge, som er beuilgit till den nye kierchis bygning sammestedtz, at de forskreffne Michel Søffrensen paa de fattigis wegne contenterer och tilfritzstiller enten med penge eller woninger igien. Flensborg den 4 maij 1638.

Hele bygningen er opført på et fundament af kampesten, som allerede fra 24. november 1636 var blevet kørt dertil fra volden. Der var dog ikke sten nok, så derfor skrev kongen til professorerne og Domkapitlet i Roskilde, at de skulle få deres bønder til at føre sten til den nye studenter-kirke, dog skulle de største sten køres på kongens Rustvogne.
Mursten blev bestilt i Holland, idet de hjemlige teglværker ikke kunne levere sten af tilstrækkelig god kvalitet. I februar 1637 indgik man kontrakt med Henrik van Dingklage i Emden om levering af tilstrækkeligt mange sten og d. 7. juli 1637 nedlagdes grundstenen til byggeriet af murermesteren Jørgen Scheffel fra Bern.

Da selve tårnet i sommeren 1640 er ved at være færdigbygget skulle toppen indrettes til observatorium, den nye bygmester Blasius var vel ikke kommet helt ind i arbejdet endnu så kongen giver anvisninger:

Udformningen af toppen ligner indretningen af Tycho Brahes Stjerneborg hvis sidelængde også er det samme som diameteren af tårnet. I bygningskontrakten med tømrermester Poul Goltz fremgår, at meningen var at opføre fem astronomiske huse på platformen ligesom på Stjerneborg.

 Byggeriet gik tit i stå på grund af pengemangel, derfor blev det pålagt de øvrige kirker i Danmark og Norge at afgive en del af deres indtægter i byggeårene, dog forsømte flere af lensmændene at indsende penge.

 Endelig stod tårnet færdigt i 1642, kirken blev først færdiggjort i 1656 og biblioteket i 1657.