Stavba původního raně barokního kostela probíhala v letech 1628 – 50, tedy za třicetileté války a těsně po jejím skončení. Kostel byl opravován po velkém požáru Všerub roku 1852. Tvoří ho obdélná loď, trojboce ukončený presbytář a mohutná hranolová věž s jehlancovou střechou. Na stavbu schodiště byla použita umrlčí prkna z okolí. Ještě roku 1989 byl kostel zpustlý a na fasádě byly vidět zásahy po střelbě z doby druhé světové války. Roku 1991 začala oprava stavby a přilehlého hřbitova, na které se podíleli i bývalí němečtí obyvatelé a řezenská diecéze.
Farností (fara (čp. 85)) byly Všeruby od roku 1650. Ke kostelu a městečku se váže zajímavá pověst. Všerubům se říkávalo žertem také „Benátky“, protože před každým domkem byla strouha s můstkem. Ve vodě se držely žáby, které se však jednoho roku příliš přemnožily. Obyvatelé se modlili v kostele a pořádali prý i procesí, aby žáby zmizely. Když začalo suchu, žáby byly najednou pryč a místní nechali žábu na památku této události zobrazit na oltáři na kamenné desce.
