Uprostred sopečného pohoria Cerová vrchovina leží v doline  prítoku Gortvy obec Nová Bašta, v okrese Rimavská Sobota.  Hoci sa prvýkrát spomína až v roku 1267 je bezpochyby staršia.

V staroveku bolo toto územie osídlené viacerými kultúrami. Na území zvanom Podmedvedie (po maďarsky Medvesalja) pod vrchom Medveš sa v 10. a 11. storočí usadila časť kmeňov starých Maďarov, ktorí sa potom rozptýlili po okolí. Dedina v minulosti patrila hajnáčskemu hradnému panstvu. Vlastnili ju Mariássyovci, Nyáryovci a iné gemerské šľachtické rody.

Jej pôvodný názov Kostolná Bašta, bol odvodený od skutočnosti, že tu sídlila farnosť pre celé okolie. Obec s opevneným kostolom bola zároveň obrannou baštou tejto oblasti. Prvý kostol zasvätený sv. Mikulášovi tu stál už pred rokom 1290. Dnešnou dominantou Novej Bašty je románsky rímskokatolícky Kostol sv. Štefana z roku 1397. Niekoľkokrát bol prestavaný, čím stratil svoju pôvodnú podobu.

V roku  1683 bola vypálená Turkami. Odvtedy sa postupne zaľudňovala. Poľnohospodárstvo, ktorým sa zaoberala väčšina jej obyvateľov je hlavným zdrojom aktivít obyvateľstva dodnes. Okrem poľnohospodárstva sa orientovali aj na remeslá, predovšetkým ako zruční kamenári či murári.