Todisteita Kuusamon kivikautisista asumustoista on löytynyt Niskajärven etelärannalla sijainneen Keinolan tilan pellosta. Sieltä on löydetty työkaluksi tai lyömäaseeksi työstetty kivi ja toinen vastaavan esineen aihio, eli kivi, johon on aloitettu reiän poraaminen.
Pysyvän suomalaisasutuksen muodostuminen tällä alueella alkoi 1600-luvun jälkipuoliskolla.
Kuusamon alue jaettiin 1700-luvulla seitsemään kylään: entisestä Kitkan kylästä muodostuivat Alakitkan, Vasaraperän ja Posion kylät ja Maanselästä Kirkonkylä, Lämsä, Poussu ja Heikkilän kylä. Tähän viimeksi mainittuun kuuluivat muiden muassa Paanajärvi, Tavajärvi, osa Suorajärveä, Vuotungit, Suiningit, Kiitämäjärvi, Heikkilä ja Kajavansalmi.
1600-luvun ajalta vanhan Heikkilän kylän alueelta mainitaan ensimmäisenä Antti Määtän ja Olli Pohjalaisen tulo Vuotunkiin ja Martti Hännisen tulo Kiitämäjärven rannalle. 1700-luvun alkupuolella Vuotungissa asui jo kaksi Määttä-veljestä ja kolmas veli muutti Suininkijärven Määttälään. Vuoden 1767 veroluettelossa Heikkilän kylässä oli jo 26 tilaa ja vuonna 1793 niitä oli 31.
Suurin osa kylästä poltettiin sodassa. Posti oli sytytetty mutta tuli sammui itsekseen. Samoin sotilaiden asuttama talo säästyi, kun tuli ei levinnyt.