Věznice Všehrdy byla spolu s Věznicí Bělušice v roce 1957 pobočkou NÚ Libkovice. S výstavbou samostatného útvaru se započalo v roce 1958 na místě bývalého statku s kachní farmou. První odsouzení byli ubytováni na špejcharu v počtu asi 30 mužů , kteří pracovali pro potřeby státního statku, později na výstavbě věznice. V roce 1960 ústav dostal od statku další 2 budovy. Byl přistavěn kinosál asi pro 100 osob , ošetřovna a přízemní budova pro odsouzené. V části statkové budovy byla zřízena kuchyně, sklady a centrální koupelna. Ve stejném roce bylo do ústavu přemístěno asi 300 odsouzených žen.
Odsouzené ženy pracovaly pro státní statek, později po vypovězení smluv byla zřízena vlastní výrobní organizace „MIVEX“, kde odsouzené ženy oplétaly bužírkou demižony. Po obdržení finančních prostředků na zlepšení podmínek ústavu se začala budovat v prostorách staré stodoly hala pro potřeby MIVEXU, kde se vyráběla konfekce. Dále zde byla zřízena výroba mozaikových dlaždic. Po adaptaci kravína bylo zřízeno pracoviště pro potřeby Elektro – Kovářská. Odsouzené ženy pracovaly i v okolních podnicích např. v Porcelánce v Klášterci n. Ohří nebo na vnitřním pracovišti PAL a Preciosy. Byla vybudována nová administrativní budova a pobočka mezi novými výrobními halami pro 10 odsouzených mužů, kteří byli zaměstnáni režii údržby. Později byla vybudována další pobočka před ústavem v odkoupeném rodinném domku, která slouží pro potřeby věznice dodnes. S výstavbou útvaru se nadále pokračovalo po etapách.
V roce 1974 byla zahájena rozsáhlá investiční výstavba útvaru tzv. nultou stavbou „vodovod“ z obce Údlice, jejímž dodavatelem byly Vodohospodářské stavby a trvala do prosince roku 1975. V listopadu 1975 zahájena stavba objektu „sklady“, která byla dokončena v prosinci 1977 (dodavatel Armabeton Praha). V listopadu 1975 započetím stavby vnějšího oplocení budoucího útvaru byla zahájena I. stavba, ukončena v prosinci 1979. Byly provedeny systémy drenáží, hrubé terénní úpravy, inženýrské sítě, objekty ubytovna pro odsouzené U1, trafostanice, strážní věže č. 2 – 5, přivaděč 22 kV, provizorní kotelna č. 1 a objekt VKT. V červenci 1976 zahájena II. stavba , která byla ukončena v prosinci 1980. Byla provedena výstavba dalších ubytoven pro odsouzené U2 – U4, objekt U5 – nástupní oddělení, příjmový filtr, prádelna a sklad intendantu pro odsouzené, kotelna č. 2, část výměníkové stanice, elektrorozvody, topné kanály a komunikace.
V roce 1979 zahájena výstavba telefonní kabelové linky Chomutov – Všehrdy. Do provozu uvedena v červenci 1979. Od května 1979 do srpna 1982 provedena akce „horkovod Chomutov – Všehrdy“. V září 1979 začala výstavba čistírny odpadních vod (ČOV) Biovit. Do zkušebního provozu uvedena v listopadu 1980. V říjnu 1979 byla zahájena výstavba 12 bytových jednotek pro příslušníky. Do užívání byly předány v květnu 1981 (projektantem GP Stavoprojekt Hradec Králové, dodavatelem Konstruktiva n.p., závod 03 Chomutov). Akce III. zahájena v březnu 1980 objektem kuchyně pro odsouzené, ukončena v dubnu 1983. Dále byla provedena technologická část výměníkové stanice a inženýrské sítě.
IV. stavba zahájena v srpnu 1980. Byly vybudovány objekty garáží, skladu PHM, garážový dvůr, tělocvična pro odsouzené, ošetřovna a příslušné inženýrské sítě. Dokončeno v dubnu 1983. V září 1983 byla jako sdružená investice útvaru, Palu Kbely a k.p. Preciosa Jablonec n. Nisou v rámci akce „hospodářská budova„ zahájena výstavba objektu kuchyně pro příslušníky včetně kantýny. Objekt dokončen v dubnu 1985. Poslední V. stavba zahájena v červnu 1982 a ukončena v listopadu 1984 . Byl vybudován objekt operační středisko, shromažďovací sál, inženýrské sítě, oplocení a strážní věž č. 6. Další samostatnou investiční akcí byla výstavba signálního a signálně zabezpečovacího zařízení celého útvaru, která započala v listopadu 1985 a byla dokončena v květnu 1988. V rámci investiční výstavby útvaru probíhala i výstavba objektů z hospodářských prostředků cizích investorů. Například výstavba distribuční a spínací stanice, výrobní hala PAL, ploškovna a třídírna k.p. Preciosa. Od roku 1987 do roku 1989 byla provedena výstavba 16 bytových jednotek pro příslušníky včetně garáží.
Postupně jak vyrůstal nový útvar, ustupovaly stavbě staré a nevyhovující objekty útvaru a přilehlého okolí. Rozsáhlá investiční výstavba útvaru se tak velkou měrou dotkla i obce Všehrdy. Výstavbě musela ustoupit řada rodinných domů a zemědělských pozemků. Útvar odkoupil a zrekonstruoval některé rodinné domky. Provedl ve spolupráci se Státním statkem Chomutov demolice chátrajících objektů. Přestavbou bývalého teletníku byla vybudována krytá střelnice. Společně s obcí bylo vybudováno koupaliště pro veřejnost, veřejné osvětlení a zastávka autobusu.