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.