Kylän vanhin asuinpaikka on ollut metsäsaamelaisten asuttama Lapinniemi Yli-Kuoliojärven etelärannalla. Autioniemessä on mahdollisesti ollut lappalaisten hautapaikka. Lappalaisyhteisön talvikylä eli Maaselän siida on ollut lähistöllä Maaselän Oijusluomalla. Saamelainen sukunimi, Ikäpäivä, esiintyy Kuolion seudulla vielä 1830-luvulla, joten he ovat asuneet Kuoliolla uudisasukkaiden kanssa ja sulautuneet paikalliseen väestöön.
Matinpoika Matero (s. 1685) saapui 1700-luvun alussa Yli-Kuoliojärven pohjoispuolelle nykyiseen Materoon. Ennen sotaa Kuoliolla oli puolenkymmentä taloa ja Vattulassa toimi kestikievari sekä koulu. Sota-aikana saksalaiset polttivat Kuolion Katajan taloa lukuun ottamatta.
Ihmisten ilmoille Kuoliolta päästiin, kun maantie saatiin vuonna 1958. Puhelin tuli 1960-luvun alkuvuosina. Sähköt saatiin vasta vuonna 1952, Kuolion vesijohtovesi vuonna 1989.
Repovaarassa säilynyt mylly on Kuusamon kotiseutumuseolla.
Kuolion kylätoimikunta aloitti toimintansa vuonna 1991. Kuolio on ollut vahvasti lestadiolaista aluetta.
Kuoliolla olevia talojen nimiä ovat mm. Hukkanen, Saunajärvi, Kataja, Vääränvaara, Lehto, Alakumpu, Palosaari, Nivala, Veteläinen, Kantoniemi, Marjala, Harjula, Ellala ja Karjalainen.
Kuolio sotavuosina 1939 – 1945
Kuolion seudun kylillä oli merkittävä asema sotavuosina – sijaitsivathan ne tärkeän Ouluntien varressa Kuusamon läntisimmässä osassa, kaukana itärajasta ja sotarintamilta.
Sotatoimialueen raja oli Kuoliolla syksystä 1939 alkaen. Kylään sijoitettiin sotilasosasto, joka valvoi Ouluntien liikennettä ja tarkasti kulkuluvat. Sotilaat olivat joko nuoria miehiä, jotka siirtyivät jonkin ajan kuluttua rintamille, tai rintamilla haavoittuneita.
Talvisodan alettua 30.11.1939 Kuusamon siviiliväki evakuoitiin Pudasjärvelle ja Oulun naapurikuntiin. Sotilaiden lisäksi Kuoliolle jätettiin talvisodan ajaksi työvelvollisia ja lottia muonitustehtäviin. Muutamissa navetoissa oli yhteensä noin 40 lehmää, joiden maito kuljetettiin Kuusamon kirkonkylään sairaalaan.
Molempien evakuointien aikana Kuolion kylä oli ensimmäinen merkittävä muonitus- ja huoltoetappi Kuusamon kirkonkylän jälkeen.
Jatkosodan päätyttyä 19.9.1944 koko Kuusamo evakuoitiin. Pohjoiseen vetäytyvät saksalaiset tuhosivat lähes kaiken vetäytymisreittinsä varrelta, myös Ouluntien varressa olevat kylät, mm. Kuolion kylän.
Peräytyvien saksalaisten jäljessä Kuusamoon tuli arviolta 10 000 venäläistä sotilasta jo syyskuun lopussa 1944. Rauhanehtojen vastaisesti sotilaita tuli Kuoliolle saakka, jossa suomalaisten rajapuomi muutettiin suomalaisten ja venäläisten joukkojen väliseksi rajapuomiksi. Se sijoitettiin Penttilänvaaran tienhaaran itäpuolelle. Venäläiset poistuivat Kuusamosta marraskuun aikana.
Puomin länsipuolella asuvien kylien asukkaat saivat palata evakosta jo lokakuun lopusta 1944 alkaen. Jouluun mennessä lähes kaikki olivat palanneet Penttilänvaaraan, Käsmään, Särkelään, Jokilammille ja Purnuun. Täysin tuhottuun Kuolion kylään paluu oli hitaampaa. Muualle Kuusamoon muuttolupia alettiin antaa yleensä vasta vuoden 1945 aikana.
Taimi Pitkäsen kielletyt kuvat kenttäradasta
Penttilänvaarasta kotoisin oleva Taimi Pitkänen (o.s. Pätsi, 1925 – 2017) tallensi Kuusamon kotiseutuhistoriaa huomattavat määrät. Sota-aikana hän otti pienellä kamerallaan kuvia elinympäristöstään, niin taloista kuin sodan jäljistä. Yksi erikoisimpia kuvauskohteita Pitkäsen tuotannossa on saksalaisten rakennuttama kenttärata. Pääosin vankien rakentama kenttärata kulki Pitkäsen kodin läheltä, joten hän pystyi kuvaamaan sitä kielloista huolimatta. Päiväkirjaansa hän kirjasi tarkasti sota-aikojen tapahtumat. Merkinnöistä oli myöhemmin merkittävästi hyötyä, kun kuusamolaisille haettiin veteraanitunnuksia.
Saksalaisten kenttärata
Saksalaiset rakensivat v. 1942 – 1944 sotavankityövoimalla kapearaiteisen rautatien Hyrynsalmelta Taivalkosken kautta Kuusamoon Vanttajankannakselle. Rata kulki Penttilänvaaran kautta. Sodan päätyttyä kenttärata purettiin ja luovutettiin Neuvostoliittoon rauhanehtojen mukaisesti, koska se oli saksalaisten omaisuutta.