1284 körül IV. László király megengedi a Hontpázmány nembéli Miklós fia Miklós részére, hogy birtokain az ország érdekében várat építhessen azzal a feltétellel, hogy a várból gonosztettet nem fog elkövetni. Egy későbbi, III. András korabeli oklevél szerint a király által megbízott Domonkos, János és Lestyák ispánok lerombolandónak mondták ki Miklós ispán név nélkül említett várát. Miklós ispán ezzel szemben védekezésül előadta, hogy a vár sok ember életét mentette meg a tatárok dúlásakor (itt az 1285-ös 2. tatárjárásról van szó). Fügedi Erik e két oklevelet Velezd várára értelmezte.
Velezd neve 1294-ben tűnik fel, ekkor a Hontpázmány nemzetség a birtokosa, akik két részletben eladták a Rátót nembéli Lóránt mesternek. A Hontpázmányok másik ága perelni kezdte az adásvételt, annak jogtalansága miatt. Végül 1347-ben országbírói ítélettel egy részét visszaválthatták. A birtok a Hontpázmányok Födémesi ágából származó Velezdi Kövér családé lett.
Velezd várát először egy 1362. 03. 15-én kiadott oklevélben említik, ekkor Velezdi Kövér János fiai: György, László és Gergely megosztoznak birtokaikon, köztük a borsodi Velezd (Werez) és Váraljavelezd (Waralyauerez) birtokokon is, amikor ez utóbbin egy várat (castrum) is említenek a birtokosztály során (galéria).
Az egri káptalan 1379. 07. 02-i oklevele szerint a nádor utasítására Kövér János fiai és Zuha-i István fia Jákó között felosztotta többek között Velezd és Váralja birtokokat (galéria). Ebben is említik a várat (loco castri).
A velezdi vár husziták általi használatára nincs adat, de egy-két közvetett bizonyíték utal rá: 1460. 08. 26-án Mátyás király Velezden ad ki oklevelet, melyben a királyi had fővezérét és erdélyi vajdát, Rozgonyi Sebestyént vezetteti be Cserépvár birtokába. Az bizonyos, hogy Mátyás a szomszédos huszita erősség, Sajónémeti rövid ostromában részt vett 1460. augusztus 28-án. Másik közvetett bizonyíték az, hogy a husziták csoportjai szisztematikusan megszállták és megerődítették a Sajó völgyében található korábbi várak helyeit (Sajógalgóc, Vadna, Sajóivánka és a már említett Sajónémetit). Bonfini viszont nem említi Velezdet az elfoglalt huszita erősségek között.
A vár pusztulására nincs adat, a későbbi, török korban való használata nem valószínű.
A várat Nováki Gyula és Sándorfi György 1992-ben felmérte: "A 307 m tszf. magasságú Vártetőt Sajóvelezd községtől Ny-ra 2,5 km-re, Putnoktól D-re 2 km-re találjuk, a Sajóvelezdről Sajónémetibe vezető mellékút felett. A laposan szétterülő hegyhát K-i vége, amely egyben a tető legmagasabb pontja, háromszög alakban végződik. Itt alakították ki a háromrészes várat úgy, hogy árkokkal és sáncokkal átvágták a két oldalról meredek háromszög szárait. A legbelső magot egy jó fenntartású, kb. 4-5 m mély és 13-15 m széles árok veszi félkörbe, a hegy K-i, kiugró éle felől is védte egy kis átvágás. Legmagasabb, ÉNy-i részén egy minden bizonnyal kerek, kb. 10 m átmérőjű kőtorony sejthető. A középső várat szintén egy hasonló méretű árok vette körbe, de ennek külső oldalán sánc is húzódik. A vár harmadik részét egy sekélyebb árok védte, amelynek feltöltődött nyomai jól kivehetők, külső oldalát ennek is sánc kíséri. E harmadik várrész É-i felében gödrök találhatók, melyekről feltehető, hogy az ostromgépek felvonulását nehezítették. Az árkok jó fenntartásúak, területüket azonban sűrű bozót fedi. A három várrész együttes hossza kb. 160 m, legnagyobb szélessége 85 m".
Források: Nováki Gyula-Sárközy Sebestyén-Feld István: B.-A.-Z. megye várai az őskortól a kuruc korig (Borsod-Abaúj-Zemplén megye régészeti emlékei 5. Miskolc, 2007); Dobosy László: Várak, várhelyek és őrhelyek Ózd környékén (Borsodi Kismonográfiák 1. Miskolc, 1975);
A légifotókat a Magyar Várarchívum Alapítvány bocsátotta rendelkezésünkre.
Sajóvelezdet elhagyva a várhegy északi oldala alatt található bányatelepnél lehet parkolni. Onnan visszafelé lesz egy jelzetlen földút a várhegy irányába, ahonnan a térképen megjelölt útvonalat követve kb. 1 km távolságra lesznek a vár sáncai. Mivel nagyon benőtt terület, érdemes lombmentes időben látogatni.
Szélesség: N - 48°16'14.7"
Hosszúság: E - 20°26'04.7"