Kong Erik Menved opførte i forbindelse med det jyske oprør i 1313 en række tvangsborge, herunder Bygholm, »for at knække jydernes stivsind«, således som der står i Sjællandske Krønike og derved tvinge de stivsindede jyder til at underlægge sig kronen. Kongen anlagde Bygholm umiddelbart vest for det nuværende Horsens. Beliggenheden af borgen indikerer, at kongemagten søgte at kontrollere færdslen i området. Mens de fleste af disse tvangsborge blev nedrevet efter kongens død i 1319, fik Bygholm sammen med Kalø på Djursland lov til at blive stående og fungerede igennem 1300-tallet som nøglefæstning i kampene om kronen og magten i Jylland. Borgen blev sammen med resten af Nørrejylland pantsat til grev Gerhard 3. af Holsten i 1331. Først ved Nebbegårdforliget d. 22. juli 1348 var Horsens med Bygholm og Kolding indløst eller i færd med at blive det og dermed atter under kongemagtens kontrol. Kongen indsatte trofaste mænd som ridderne Peder Iversen Lykke og Jens Andersen Brock som høvedsmænd på Bygholm, og under det store jyske oprør mod kong Valdemar Atterdag 1368‑72 var sidstnævnte i stand til at holde borgen. Bygholms store betydning ses bl.a. af, at det i resten af middelalderen var betydningsfulde folk, der sad som lensmænd her eller havde lenet i pant.
Bygholm forfaldt i slutningen af 1500-tallet, og i 1616 lod Christian 4. lensmanden flytte over på lensgården Stjernholm, som Bygholm blev lagt ind under. I 1661 tilskødede Frederik 3. både Bygholm og Stjernholm til Peder von Uffeln fra Hamborg, der i 1670 solgte dem videre til Joachim Werner Bülow, der lod det forfaldne anlæg nedrive. Stenene blev genanvendt til at genopføre Bygholm, der atter blev herregård; den nuværende bygning er dog først opført i 1775.
