První zmínky o obci jsou dle kronik datovány mezi 11. a 13. století, ale první listinné záznamy v českém jazyce jsou až z roku 1492, kdy získal Jan Pňovský koupí hrad Sovinec. Jak vznikl název obce, se již asi nedá zjistit, ale některé prameny uvádějí souvislost se jménem zakladatele (lokatora) obce, který se nazýval Stoel, nebo Stohler a jiné uvádějí souvislost s některou štolou (Stohl) v této oblasti. V severozápadní části obce na vyvýšenině stojí kostel Nejsvětější Trojice v pozdně gotickém slohu a z její věže dává krásný rozhled po okolí. Kostel byl postaven v letech 1576 - 1606 Janem Kobylkou z Kobylího.
