Paltalinna, alun perin Kiehimän seurojentalo, on valmistunut vuonna 1927. Paltalinna on toiminut myös suojeluskunnan kokoontumispaikkana. Paltalinnaa olivat rakentamassa samat kirvesmiehet, jotka olivat mukana lähes kaikissa sen ajan tärkeimmissä rakennuskohteissa. Paltamossa oli taitava kirvesmiesporukka, johon kuului mm. Kalle Pulkkinen, Ilmari Pulkkinen, Ilmari Möttönen, Hannes Möttönen ja Uuno Pulkkinen. Paltalinna on rakennettu hirsistä käyttäen todella jykeviä hirsiä erikoisella tavalla kattorakenteissa. Hirret oli ostettu Kajaani-yhtiöltä..

Nykyään Paltalinna on kunnan omistuksessa, ja se on remontoitu nykyaikaisempaan muotoon. Esim. sisävessat laitettiin remontin yhteydessä.