Paltaniemi, en ca 15 km lång udde vid ö. stranden av Ule träsk, hörde tidigare till Paltamo, men anslöts 1954 till Kajana lk. På udden, som numera ligger inom Kajana stad, finns bl.a. Kajana flygfält (invigt 1956), Paltamo forna, av trä byggda kyrka (J. Knubb, 1726) och ett Eino Leino-museum, uppfört som en kopia av författarens barndomshem och invigt 1978. Kyrkan är en av landskapets förnämsta sevärdheter, invändigt rikligt försedd med målningar återgivande bibliska motiv av Emanuel Granberg från åren 1778 -81. Altartavlan från 1727 är utförd av Margareta Capsia, landets äldsta kända kvinnliga målare. Kyrkan tillhör fortfarande Paltamo församling. I Paltaniemi förevisas även en byggnad ("kejsarens stall"), i vilken kejsar Alexander I spisade middag 1819. (R. Heikkinen, Kainuun kulttuurin kehto: retki Paltaniemelle, 1993)