História školy, ktorá nesie v súčasnosti meno významného zberateľa slovenských rozprávok, farára Pavla Dobšinského, sa začala písať už v roku 1975. Z iniciatívy vtedajšieho vedenia okresného štátneho orgánu, ONV v Rimavskej Sobote, bolo rozhodnuté o položení základného kameňa 36-triednej Základnej deväťročnej školy v Rimavskej Sobote, časť Tomašová. Dňa 3. novembra 1975 sa uskutočnila slávnosť k tomuto aktu. Brány novej školy, ZŠ na Ul. víťazstva sa otvorili dňa 4. septembra 1978. Do krásnych nových tried zasadlo 482 žiakov zatiaľ len I. stupňa. Od začiatku mala škola internacionálny charakter vďaka triede s ruským vyučovacím jazykom pre deti vojakov zo sovietskej posádky. Ich prítomnosť prispela k výchove žiakov k tolerancii a inonárodnej znášanlivosti. Plnoorganizovanou školou sa stala 1. septembra 1979, kedy začalo školu navštevovať 450 žiakov I. stupňa a 375 žiakov II. stupňa. Pedagogický zbor pozostával zo 70 členov.
Počas prvých troch rokov existencie súperila škola s problematickým stravovaním žiakov. Objekt jedálne ešte nebol dokončený a strava sa dovážala a vydávala v provizórne zariadenej jedálni v 5. pavilóne. Úplná prevádzka školy bola zabezpečená v školskom roku 1981-1982, keď bol 15. septembra odovzdaný objekt školskej družiny s 11 oddeleniami a školská jedáleň a kuchyňa. V 5. pavilóne sa dobudovali špeciálne učebne, čím sa vytvorili podmienky potrebné na kvalitné vzdelávanie žiakov.
7. mája 1982, za prítomnosti ministra školstva SSR a generálneho konzula ZSSR v Bratislave, sa uskutočnila slávnosť k čestnému pomenovaniu školy: Škola Československo – sovietskeho priateľstva. V kronike školy môžeme nájsť ďakovné a pekné slová 6 učiteliek z ruského mesta Tula, ktoré školu v roku 1983 navštívili a veľmi pochválili. Vzdelávanie vo viacerých jazykoch má na škole pevnú a dlhú tradíciu, o čom svedčí aj otvorenie triedy s rozšíreným vyučovaním cudzích jazykov od 3. ročníka. Žiaci mali možnosť vybrať si zo štyroch svetových jazykov–anglického, nemeckého, francúzskeho a ruského.
2. septembra 1983 otvorila svoju pobočku n škole Okresná knižnica v RS(dnes Knižnica M. Hrebendu), ktorá prispela k rozvoju čitateľskej gramotnosti žiakov.
V roku 1993 vznikla trieda s rozšíreným vyučovaním matematiky a prírodovedných predmetov. Škola svojou činnosťou a horlivou prácou pedagogických i nepedagogických zamestnancov mala už v tomto období pevnú a najlepšiu pozíciu medzi školami podobného typu v okrese Rimavská Sobota. Žiaci patrili k najlepším v reprezentácii školy vo všetkých oblastiach. Dňa 6. októbra 1995 sa uskutočnil slávnostný akt prepožičania čestného názvu Základná škola Pavla Dobšinského, ktorý podnietil učiteľov a žiakov k zriadeniu Pamätnej izby Pavla Dobšinského. Zámer sa stal skutočnosťou dňa 28. marca 1996. Od slávnostného prestrihnutia pásky sa pamätná izba stala miestom, kde ožila minulosť a prostredníctvom rozprávok Pavla Dobšinského sa žiakom vštepuje láska k slovenskému národu a jeho tradíciám.
V roku 1996 sa otvorila trieda so zameraním na športovú prípravu. V roku 1997 na základe Programového vyhlásenia vlády SR a z neho vyplývajúcej koncepcie starostlivosti o talentové a nadané deti, bola ako jediná v kraji otvorená trieda pre všeobecne intelektovo nadané deti.
Od 1. januára 2002 je škola samostatným právnym subjektom.
Prvým riaditeľom školy bol Vladimír Morvay, ktorý bol roku 1982 v rytierskej sieni Bratislavského hradu vyznamenaný ako zaslúžilý učiteľ a vo vedení školy ostal do roku 1984. Jeho nástupníci Mgr. Vladimír Repa(1984-1991), PaedDr. Július Sojka(1991-1995), Mgr. Alena Kobelovská(1995-1999), Mgr. Ivan Gecko(1999-2009) a RNDr. Peter Nôta(2009-2019) prispeli svojím poctivým a úprimným prístupom a prácou k dobrému menu školy. Skvalitňovať a modernizovať výchovno-vzdelávací proces napomáha i súčasné vedenie školy, ktoré nastúpilo v školskom roku 2019/2020 pod vedením Ing. Eriky Demkovej.
