Kainuun asuttamisen ensimmäisessä vaiheessa 1500-luvun puolivälissä ei Korhos-sukuisia asukkaita vielä Kainuuseen ilmaantunut. Rappasota 1570–1595 hävitti tämän ensiasutuksen aallon lähes kokonaan Kainuusta, mutta Täyssinän rauhan myötä Kainuun liittäminen yhteisellä rauhansopimuksella Ruotsin vallan alle mahdollisti Kainuun uudelleen asuttamisen. Uudisasukkaat saivat Ruotsin kuninkaan Kaarle IX päätöksellä 6 vuoden verovapauden. Verovapaus houkutteli Kainuuseen uusia asukkaita, ja tämän toisen asutuskauden aikana ilmaantui Sotkamoon Vihtamoon myös ensimmäinen Korhonen-sukuinen asukas. Tämä Olavi (Olof) Korhonen s. noin 1573 on Sotkamon Korhosten kantaisä.

Ensimmäiseen Sotkamoon tulleeseen Korhoseen liittyy sukutarina:

Sukutarinan mukaan isällä oli Karjalan Kannaksella kotona kolme poikaa, kun tuli tieto, että pohjoisessa saa verovapaita talon paikkoja. Vanhin poika ei innostunut, koska hän saisi perinnöksi isän tilan. Innostus iski nuorempiin poikiin lähteä etsimään verovapaa oma tila, koska
kotitanhuvilta sitä ei saisi. Vaihtoehtona olisi kolmannen pojan armeijaan joutuminen.

Matka kotoa alkoi luvatuille verovapaille maille heti, kun matkalle tarvittavat lupalaput olivat taskussa. Pohjois-Savossa matkatessaan he osuivat hyvin kauniiseen korpimetsän siimekseen. Sitä ihailtuaan toinen veli päätti, että hänelle tuleva talo rakennetaan siihen paikkaan. Yhteisvoimin he ryhtyivät taloa rakentamaan.

Talon valmistumisen jälkeen kolmas poika jatkoi perheineen matkaansa ja saapui Sotkamoon, sitoi lehmänsä puuhun ja ensi töikseen rakensi turvemajan tilapäiseksi asunnoksi. Kaadettuaan hirsiä uudispirttiin hän poltti loput puut ja risut kaskimaaksi kylväen siihen naurista, ruista ja
ohraa.

Toisaalta Savossa tiedetään Nilsiästä, että sinne on muuttoluvan mukaan tullut Karjalan Kannakselta mies nimeltä Peer Korhonen. Nilsiään Peerille oli rakennettu niin iso talo, että hän ei yksin pystynyt sitä rakentamaan. Hänellä on tarvinnut olla ainakin yksi tai useampi apumies.
Lisäksi uskotaan, että Sotkamoon matkaa jatkanut henkilö oli tämä toinen rakennusmies, koska lähiseudulla ei asunut miehiä.

Savoon jäänyt veli olisi silloin ollut Sotkamoon saapuneen Olofin nuorempi veli, koska nuorempaa oli tapana auttaa.

Lähde; Korhosten sukujuuret ja sukuhaarat Kainuussa. Kainuun Korhoset.