Drømmen om en skole
Skolens ældste bygninger er klosterbygningen, hvis fundament stammer tilbage fra 1100-tallet, hvor en gruppe benediktinermunke slog sig ned og opførte Skovkloster. Under Reformationen i 1536 inddrog Kong Christian III kirkens jord, således også Skovkloster i Næstved. Kongen blev selv den øverste myndighed i gejstlige anliggender og de eksisterende munkeordner gradvist afviklet. De fleste munke ved Skovkloster fik tilladelse til at blive i en overgangsperiode, hvilket ikke var usædvanligt. De sidste munke forlod Skovkloster i 1559 og tog til Antvorskov ved Slagelse.
Herluf Trolle overtager Skovkloster
Den daværende konge, Frederik II, fik derfor muligheden for at tilbyde det tidligere kloster til Herluf Trolle i 1560 som del af et mageskifte, hvor kongen til gengæld overtog Hillerødsholm, der derefter blev til Frederiksborg Slot. Herved fik kongen et sammenhængende jagtområde i Nordsjælland. Efter Herluf Trolles overtagelse af klosteret, blev det navngivet Herlufsholm.
Herlufsholm bliver til en skole
Skolen blev stiftet d. 23. maj 1565 som en skole for "20 sønner af adlen og 20 sønner af andre ærlige mænd". Således skulle skolen rette sig til både sønner af adelen, men også til de sønner, der havde lyst og evner til lærdom og dannelse. Herluf Trolle nåede dog aldrig at se sin drøm realiseret. I sommeren 1565 blev han endnu en gang kaldt i krig, og som flådens øverste admiral under Den Nordiske Syvårskrig. Han satte sejl mod den svenske flåde ved Femern. Under slaget d. 4. juni blev han dødeligt såret, og senere samme måned gik han bort.
I sin mands fravær blev Birgitte Gøye skolens første forstander.