První písemná zmínka o Kamenné pochází z r. 1385. Tehdy obec patřila k hradu Brníčko a s ním se v rámci tzv. Zálesí kolem Rohle dostala v roce 1446 k panství Zábřeh. Po třicetileté válce zde zcela mizí některá česká jména. Podle lánového rejstříku z roku 1677 bylo v Kamenné jenom 17 usedlíků, takže patřila mezi menši vsi zábřežského panství. Roku 1834 zde bylo 60 domů a 408 obyvatel. Po roce 1848 tvořila Kamenná nejvýchodnější část politického a soudního okresu Zábřeh.
Vzhledem ke svažitým a málo úrodným pozemkům se značná část obyvatel zabývala domáckým tkalcovstvím a výrobou různých sít. Z této tradice vyšel místní podnikatel Johan Anderlitschka, který po roce 1848 postupně rozšiřoval výrobu drátěného pletiva až po založení továrny na drátěné výrobky v roce 1873. V roce 1908 vznikl v obci i menší závod na výrobu kartonáže.
Kamenná tvořila důležitou výspu němectví ve východní části Zábřežska. Bylo příznačné, že národní slavnosti, které se konávaly každoročně pod Bradlem, organizovali Němci nad Kamennou a Češi na druhé straně nad Lipinkou. Německá obecná škola v Kamenné však vznikla až v roce 1881. Předtím chodily zdejší děti do školy v Rohli.
Po květnu 1945 byla obec velmi rychle osídlena českými rodinami, v mnoha případech ještě před odsunem Němců.
Původní vesnická zástavba se změnila koncem 19. století po výstavbě továrny a zejména v posledních desetiletích, kdy zde byla postavena celá skupina vícepodlažních obytných domů.
Počet obyvatel v obci až do roku 1900 stoupal. Tehdy zde bylo 553 obyvatel v 64 domcích, ale potom začal pomalu klesat a tento trend dosáhl vrcholu po odsunu německého obyvatelstva. V roce 1930 zde bylo jen 18 Čechů. V roce 1950 žilo v této obci 367 usedlíků v 84 domech. Pod vlivem zdejší továrny v následujícím období obec opět rostla a v roce 2001 měla již 590 obyvatel, kteří žili sice jen v 92 domech, avšak v dvakrát větším počtu domácností, což je u venkovské obce dost výjimečné. Od roku 2002 vlivem snižování počtu zaměstnanců v místním závodě má počet obyvatel klesající tendenci. V současné době má obec kolem 500 obyvatel a 125 rodinných a bytových domů.
