A többi környékbeli településhez hasonlóan, Mályinka történelme is egészen az Árpád-korig nyúlik vissza, bár a falu határában talált leletek tanúsága szerint már a kőkorszakban is éltek itt emberek, és Mályinkán találták megaz újkori bükki kultúra egyetlen sírleletét. A népvándorlás idején hun, avar és szláv népek telepedtek le, majd Bors vezér magyarjai és a kabarok szállták meg a vidéket.
Nevének jelentése nem határozható meg pontosan. Egyes források a szláv „malim”, azaz „eper” szóból származtatják, mások a „mál”, azaz „hegyoldal”, illetve annak kicsinyítő képzővel ellátott alakjából eredeztetik.
Mályinka községet Mályinka néven 1254-ben említik először okleveleink. Ettől az időtől kezdve dédesi várbirtok. Dédes eleste után a törököknek adózott. A falu magyar jobbágyai elszöktek, helyükre részben szlovákok költöztek, akik azonban hamarosan beolvadtak a magyarságba. 1785-ben épült református temploma. Szintén 1785-ből származik a fa harangláb. Harangját 1763-ban Losoncon öntötték.
A helyi lakosok életmódját meghatározta az erdő közelsége, az állandó alkalmazkodás a természet kihívásaihoz, így az erdő jelentette az egyik legfontosabb megélhetési lehetőséget is, a szénégetést.