Først under Frederik II kom der for alvor gang i bygningsforbedringerne. I foråret 1574 begyndte en byggeplads at brede sig med skure, værksteder og dynger af materialer. Som bygmester antog kongen Hans van Paeschen, der formentlig stammede fra Holsten. Han skulle blandt andet styre de hundredvis af håndværkere, der kom i arbejde de følgende år: murere, kalkslængere, stenhuggere, tømrere, arbejdsmænd og vævere. En ikke uvæsentlig del af disse var ”importerede” erfarne og dygtige håndværkere, især fra Flandern.
Byggematerialerne blev hentet langvejs fra. I Norge blev store træer fældet, og tømmeret blev oplagret, indtil der kom skibe fra Danmark for at hente det. På Gotland hentedes også tømmer sammen med store mængder sandsten, og fra Helsingborg hentedes senere yderligere sandsten. Den gotlandske sandsten er blød og blev brugt udvendigt til dekorationsrige balustrader og omgange på tårne samt til bånd, gesimser, vinduesindfatninger og ikke mindst portaler med dekorationer og figurer. Indvendigt kunne den gotlandske sten iagttages i kaminer, vindeltrapper og ornamenter. Den skånske sten, Helsingborgstenen, der er hårdere og derfor egnet til glat arbejde, anvendtes primært til den senere facadebeklædning.
Arbejdet startede for alvor i 1574 med forlængelsen af det oprindelige middelalderhus i ringmurens nordøstlige hjørne, som på daværende tidspunkt udgjorde nordfløjen. Der blev opført nye porthvælv, hvorover kongen skulle have sit kammer med karnap og udsyn over sundet. I den forbindelse opførtes også det trappetårn, som i dag benævnes Dronningetrappen. Efter nordfløjen opførtes vestfløjen – hvorved nordfløjen forbindes med stenhuset – og Palatiebygningen (Palatiet), der ligger op til sydvesthjørnet af ringmuren. Omtrent sideløbende blev Palatiet forbundet med det tredje middelalderlige stenhus i sydøst, hvori slotskirken blev indrettet. Mellem kirken og det store tårn (senere benævnt Telegraftårnet) blev indrettet en stor sal.
Omkring 1577 var byggeriet ved at være afsluttet, og Kronborg, som Krogen efter kongens befaling nu skulle hedde, fremstod med røde teglmure med bånd og vinduesindfatninger med overliggende trekantfelter, hvor groteske små hoveder kigger frem i sandsten. Øverst kronedes bygningen af kraftige vægtergange med dekorationer, ligeledes i sandsten. Tagene var dækket med røde tegl importeret fra Emden.
Men kongen var allerede i gang med nye planer, og han havde råd til det. Sundtolden, som var kongens private indtægt, gav enorme beløb. Den kunne han kunne bruge efter forgodtbefindende i modsætning til de indenlandske skatter, der var under rigsrådets kontrol. Kongen har sikkert drømt om et hvidt slot, allerede inden byggeriet sluttede. I 1579 skrev han kontrakt med malere for at få overstrøget sydfløjen med linolie og blyhvidt. Samtidig blev vandspyene, der ledte regnvandet bort fra fløjens vægtergange, malet med zinnober og mønje – måske som grundlag for en senere forgyldning. Den malede facade blev dog kun et mellemstadie, for 4. januar 1580 indgik Frederik II aftale med flere murermestre, som skulle beklæde Syd- og Vestfløjen med sandstenskvadre fra bruddene ved Helsingborg.
Kongen beskrev selv i detaljer, hvordan murerne skulle arbejde. Han skrev blandt andet at, ”Den gamle mur skal uddybes en halv alen ind, så dybt at den skånske huggen sten kan indmures”, og for hvert fjerde skifte skulle der hugges en hel alen ind, så bindere kunne indmures.
Det viste sig på samme tid, at de importerede tagsten ikke kunne klare det barske klima på Kronborg med påvirkninger fra havet. Allerede efter få års forløb var regnen slået ind under taget på nordfløjen, hvor det havde fået loftsbjælkerne til at rådne.
Et tættere og mere uforgængeligt tagmateriale var kobberplader, og i tilgift fik man så skønheden ved både de blanke og de senere grønirrede tagfladers samspil med sandstensfacaderne. 1579 gav kongen ordre til at skaffe kobber til spir og vindfløje, og året efter fulgte en større ordre på 100 skibpund (ca. 16 tons) kobberplader. For at få udført de omfattende arbejder indforskrev kongen kobbertækkere, blandt andet fra Hamborg.
Men ikke engang Øresundstoldens pengekiste var bundløs, og man blev nu nødt til at betale med smør, korn og andre varer. Samtidig var der ustandselig vrøvl med håndværkerne, og kongen syntes, at han, i stedet for den perfekte fyrstebolig, havde fået en permanent byggeplads. Antonius von Opbergen, som havde afløst Hans von Paeschen, blev af kongen gjort ansvarlig for at have forsinket byggeriet på Kronborg. Kongen greb selv ind ved i 1584 at skrive til borgmestrene i alle sine købstæder, at de skulle ”forskaffe hid ufortrødent alle de murermestre og murerkarle, som findes udi Eders by”.
Hvor mange murere, der rejste over hals og hoved, ved man ikke, men der må være kommet gang i byggeriet. Ud på efteråret 1584 fik bygmesteren Antonius von Opbergen fuld oprejsning, og i november 1585 var Kronborg i det væsentlige færdig, og kongen har sikkert åndet lettet op. På dette tidspunkt var hovedvolden blevet udstyret med omfangsrige kassematter i form af Ridderpostejen og Strandpostejen.