Rakstos pirmoreiz minēta 12. gadsimtā. No 1569. gada Rečas Pospoļitas sastāvā. Pēc Polijas otrās dalīšanas 1793. gadā Stoļina iekļāvās Krievijā. No 1921. līdz 1939. gadam tā atradās Polijas sastāvā. 1939. gadā Stoļinu ieņēma PSRS karaspēks. Otrā pasaules kara laikā to ieņēma vācu karaspēks. Pēc Otrā pasaules kara — Baltkrievijas PSR sastāvā. No 1991. gada — Baltkrievijā.
Stoļina ir lodesgrūdējas Nadzejas Astapčukas (Надзея Астапчук, 1980) dzimtā pilsēta.