Podľa tradície založili obec korytári z Budína, pričom toto remeslo v obci pretrvalo až do polovice storočia. Prvá písomná zmienka z roku 1393 uvádza názov Brtolehutaya. V neskorších prameňoch sa uvádza názov Budalehota (1467) či Budaszállás. Názov Budiná sa začínal používať koncom 18 storočia. Podľa tradície založili obec korytári z Budína, pričom toto remeslo v obci pretrvalo až do polovice 20. storočia. Osada najprv patrila pod Divínske hradné panstvo, od roku 1554 do 1595 pod Sečiansky sandžak. V rokoch 1585-1586 bol vlastníkom Budinej Mohamad bin Ali. Po vyhnaní Turkov sa Budiná znovu ocitla v majetku Divínskeho hradu.
Za vlády Balassovcov prijalo obyvateľstvo Budinej podľa vzoru „Cuius regio, eius religio“ reformáciu. Obec patrila pod matkocirkev Polichno. V roku 1686 sa novými pánmi divínskeho panstva stali Zichyovci, ktorí sa začali snažiť o rekatolizáciu poddanských obcí. Evanjelické učenie však medzičasom na Budinej silno zakorenilo. Podobrotky sa Budinú rekatolizovať nedarilo, a tak boli všetci dospelí muži v roku 1717 uväznení na haličskom zámku, kde ich donútili platiť dávky (štólu) divínskemu plebánovi. Táto situácia podnietila Jána Madácha k osobnej audiencii u Márie Terézie.
Ekonomický tlak mal svoje ovocie, nakoľko v období zavedenia tolerančného patentu už bola Budiná znovu spolovice katolícka. Samostatný ev. a.v. zbor vnikol na Budinej až v roku 1856, dovtedy bol zbor administrovaný z Polichna. Katolícki veriaci patria stále pod divínsku farnosť.
V roku 1890 vyvolala pozornosť vzbura roľníkov, ktorú podnietilo nespravodlivé rozdelenie pozemkov. V roku 1895 postihol Budinú veľký požiar, ďalší vypukol 18. októbra 1935. Iba krátku históriu mala ťažba kremeňa (albitu a chloritov) v lome pod Javorom, v súčasnosti je toto ťažobné miesto zatopené.
Počas Slovenského národného povstania bolo do povstaleckej armády zmobilizovaných 127 mužov, ďalší odišli k partizánom. Po porážke povstania boli mnohí Budinci internovaní v nemeckých pracovných táboroch. V decembri 1944 a januári 1945 podnikli nemecké jednotky trestné výpravy do okolia Budinej, podnietené zavraždením a olúpením dvoch nemeckých vojakov. Zajali trinásť partizánov a šesť obyvateľov Budinských lazov. Odvliekli ich do Piešťa, kde ich mučili a 24. januára 1945 bosých hnali nazad na Budinské lazy. Tam ich pri osade „Šajtárovci“ na výstrahu obesili. Na pamiatku popravených bolo toto miesto vyhlásené za Pamätný les pri Budinej.
Na vŕšku nad Budinou v 60. rokoch 20. storočia postavili obeseným pamätník, ktorý sa stal za socializmu najexponovanejším miestom pre náučné antifašistické výlety a slávnosti v Lučenskom okrese. Ďalší pamätník odhalili priamo na mieste popravy v roku 2006.
Budiná sa pripomenula svetu v roku 2001, kedy víchrica a mráz polámali stromy a obec sa ocitla na dlhý čas bez elektrického prúdu.
Obec má charakter kombinácie hromadnej dediny a lesníckeho osídlenia. Zástavbu z 19.storočia charakterizujú zrubové a murované domy, omietnuté a obielené, s valbovou strechou.