Ozemlje, na katerem danes stoji vila Herberstein, je imel sprva v lasti kmet Devčnik. Leta 1857 ga je prepisal na hčerko Ano in njenega moža Bartolomeja Novaka. Del posestva sta leta 1886 prodala baronici Marii Ritter de Zachony, ki je v Velenje prišla zaradi poroke svoje hčere Gizele z grofom Karlom pl. Adamovičem, takratnim lastnikom gradu Velenje. Na posestvu je dala postaviti vilo. Načrte zanjo je v letih 1886 in 1887 izdelal dunajski arhitekt Otto Hieser. Na njen izvor spominja hišni grb nad vhodnimi vrati, ki se je ohranil vse do danes. Vila se je sprva imenovala Waldek in je bila zgrajena v pozno historičnem slogu kot plemiška rezidenca na podeželju.
Ljudsko izročilo pravi, da je bila gradnja vile pogubna za tesarskega mojstra Andreja Hudovernika, ki je glede izdelave ostrešja sklepal pogodbo z naročnikom. Ogledal si je načrte za vilo in se pogodil za ceno, vendar se je kasneje izkazalo, da je prenizka. Ker je moral naročilo dokončati, se je močno zadolžil, prodati je moral vse svoje imetje z gozdovi vred, obdržati pa mu je uspelo le hišo pod hipoteko.
Grb nad vhodnimi vrati je razdeljen na zgornjo in spodnjo polovico, nad njim pa je krona s tremi jagodovimi listi. Na zgornji polovici je upodobljena moška, v komolcu upognjena desna roka na zlati podlagi, ki drži pastirsko palico. Spodnja polovica je modra s tremi zvezdami, razporejenimi v navzdol obrnjen trikotnik. Kljub večkratni menjavi lastnikov se je hišni grb prvih lastnikov ohranil do danes.
Leta 1898 je posestvo z vilo, ki se je takrat imenovala vila Ritter, kupil Jožef pl. Eder in do leta 1912 dokupil še nekaj dodatnega posestva. V času njegovega lastništva se je vila imenovala Novi Šalek. Po njem se je imenoval tolmun na Paki blizu današnjega mostu na Kidričevi cesti proti Šaleku – Ederjev tunf. Tja se je hodil kopat ne glede na letni čas in vreme. Pozimi in poleti, v soncu, dežju ali snegu. Pritekel naj bi v kopalnem plašču, se gol okopal in stekel nazaj v vilo. Tolmun je bil dolg 12 metrov in globok poldrugi meter.
Grb nad vhodnimi vrati vile je razdeljen na zgornjo in spodnjo polovico, nad njim pa je krona s tremi jagodovimi listi. Na zgornji polovici je upodobljena moška, v komolcu upognjena desna roka na zlati podlagi, ki drži pastirsko palico. Spodnja polovica je modra s tremi zvezdami, razporejenimi v navzdol obrnjen trikotnik. Kljub večkratni menjavi lastnikov se je hišni grb prvih lastnikov ohranil do danes.
Zunanjost vile: Že od nekdaj ima rumeno fasado, pred drugo svetovno vojno pa jo je preraščala popenjavka glicinija z 20 centimetrov dolgimi vijolično-modrimi cvetovi. Nad balkonskimi vrati je v gotici pisalo Dieses Haus ist in Gottes Hand, Neu Schallegg ist benannt. Vila je imela pet dimnikov, vsak je bil drugačne oblike. Ko so nazadnje prekrivali streho, so podrli vse dimnike razen enega, ki jo krasi še danes. Njihovi ostanki so vidni na podstrešju. Na vrhu strehe sta kovinska ploščica v obliki puščice s črkama E. J. in letnico 1898, ki se v vetru vrti, ter kovinska krogla z bodicami. Okna in vrata v pritličju so bila zavarovana s kovanimi okrasnimi mrežami in današnja so povsem enaka prvotnim.
Notranjost vile: Levo od vhoda v vilo je bila knjižnica, kjer so bile po vseh stenah od tal do stropa police s knjigami. Druga vrata levo so vodila v jedilnico. Ta je bila manjša, za vsakodnevno uporabo. Druga, večja jedilnica je bila namenjena za gostitev večje družbe in posebne priložnosti: rojstne dneve, ženitve, krste … Kasneje si je grof Hulan tu uredil spalnico. Vrata v kletne prostore so morala biti vedno zaprta, ker v vili ni smelo biti vonja po hrani, ki se je pripravljala spodaj.
