Uhelnou bychom v rejstříku obcí do roku 1948 hledali marně. Stejně jako dnes původní Sörgsdorf

Nejstarší dějiny obce známe díky zakládací listině nedalekých Vlčic, kde je zmíněn lokátor jakýsi Pribista, který je obecně považován za zakladatele Uhelné. Historik Rudolf Zuber připomíná, že první kolonizace zdejší krajiny byla podle listin zřejmě slovanská, a že Šora či Šorik mohl být jedním z potomků zakladatele obce, který se později stal prvním šoltýšem. Další syn měl údajně dostat hospodářský dvorec, jehož parcelací později vznikla jedna z částí dnešní integrované osady Dolní Fořt.

První zmínka o vesnici se objevuje už v roce 1290, a uvádí, že k obci patřilo 20 lánů pozemků a přináležela pod správu z Javorníku. Zajímavé je, že později se výměra pozemků významně zmenšila, což mohlo znamenat, že část obce zanikla.

V té době, tedy v 16. století zde žilo 13 selských rodin, 12 zahradníků a už tehdy i tři hrnčíři. Obec velmi postihla třicetiletá válka, ale naštěstí zpustl jen jeden jediný grunt. V roce 1735 vzniká na hranicích katastru s Vlčicemi nová osada jménem Zastávka, dnes bohužel už bez stálých obyvatel.

Kromě zemědělství, prací v lesích a pastvinářství byla hlavním zdrojem obživy místních obyvatel textilní produkce a také hrnčířství a cihlářství, To i díky kvalitní hlíně těžené v místě dnešní hlavní silnice do Jeseníku. K šoltéství patřila také pila a výrobna potaše.

K obci kromě zmíněné Zastávky patřila osada Fořt, kterou tvořily tři části se zvláštními názvy Dolní Fořt - Priebnerovi zahradníci, Dolní Fořt - Mlatci a Horní Fořt.

Od nejstarších dob byla obec přifařena do sousedních Vlčic, popřípadě po jejím zrušení v roce 1582 až do Skorošic. V roce 1678 byla fara ve Vlčicích obnovena a k ní patřila i dnešní Uhelná. Nejprve byla ve druhé polovině 18. století vybudována na návsi menší kaple sv. Floriána. V lednu roku 1792 odkázala ve své závěti nemalou částku 3 050 zlatých na stavbu kostela v Uhelné bezdětná manželka někdejšího ranhojiče z Javorníka a dědička části zdejšího šoltéství Kateřina Freundová. Darovala také 6 000 zlatých na obživu chudých farníků. Úroky z věnovaných peněz nakonec částku ještě navýšily, a tak z nich mohla být postavena ještě škola a fara.

V roce 1801 byla stavba zahájena a v roce 1803 dokončena. Toto datum nese také průčelí jednolodního chrámu, který je poměrně velký. Od roku 1801 se navíc chlubí tím, že se jedná o farní kostel, neboť se Uhelná stala novou farností. A kostel byl po dokončení zasvěcen  patronce štědré donátorky sv. Kateřině.

Památkou značného významu je v kostele objevená  dřevěná gotická socha sv. Barbory pocházející z 15. století. Jak se do chrámu dostala, není vůbec jasné. Pravděpodobně sem byla převezena z některého z kostelů či kaplí v okolí. Dnes je k vidění na javornickém zámku.

Kromě toho ve vesnici najdeme i další drobné sakrální památky, byť kaple sv. Floriana už bohužel nestojí. Pozoruhodnou památkou a připomínkou zdejších cihlářů je obloukový most přes Lánský potok vyzděný z místních cihel.

Významnou památkou na dějiny obce je také vodní hladina jezera Pelnář východně od zastavěné části vesnice. Jedná se o původní důl na lignit, jehož těžba dala vesnici nové jméno. Uhlí zde bylo objeveno už v roce 1858 a o tři roky později se začalo těžit v povrchovém dole. Nejvíce uhlí se zde vytěžilo za rok kolem 22 000 tun, ale pak už produkce klesala. Důl, kterému dal jméno Antonín Pelnář, kdysi ředitel firmy Východočeské uhelné doly, se definitivně uzavřel v roce 1957. Dnes slouží jako rekreační a odpočinková zóna.