Kamionna istnieje już ponad 600 lat, o czym świadczy zapis z 1398 roku, z którego możemy się dowiedzieć, że Kamionna - zwana "Kamona" (lub "Ossicowica") była wtedy lokowana i należała do potomków Zbigniewa ze Szczyrzyca. W późniejszym czasie Jan Długosz w swoim dziele "Liber beneficjorum (II, 178)" nazywa ją "Kamyona" i "Osszykowa" (czyli Osikówka). W drugiej połowie XVI wieku nazwa zmieniła się na "Kamionka".
      W roku 1581 osada stała się własnością Urbana Łapki herbu Drużyna. Obejmowała wtedy 2,5 łanu kmieckiego. W roku 1629 przeszła w ręce Gabońskiego i to on najprawdopodobniej przekazał Kamionkę Jezuitom przy kościele Św. Piotra i Pawła w Krakowie. To wtedy, czyli około roku 1649 minister jezuitów ks. Ignacy Golanowski odnotował Kamionną w "Księdze relacji grodzkich krakowskich". Poza opisem budynków folwarcznych, komór i gruntów wymienionych, wymienił m.in. 9 kmieciów wraz z ich powinnościami i daninami.
       W 1656 r. podczas potopu szwedzkiego, książe Jerzy Lubomirski wraz z okolicznymi chłopami pobił tutaj Szwedów maszerujących z Krakowa do Sącza. Nie była to duża bitwa, ale książę upamiętnił ją wystawieniem obelisku znanego dzisiaj pod nazwą "Kolumna szwedzka". 
       Po rozbiorach, w 1816 r. teren wioski zwanej już "Kamionna" został skonfiskowany przez austriackiego zaborcę jezuitom i znalazł się w rękach prywatnych. Franciszek Ożegalski, kupił majatek Kamionna po 1863 roku dla swojego syna Józefa Ignacego.
      W "Słowniku geograficznym Królestwa Polskiego i innych krajów słowiańskich" - Tom III, wydanym w  Warszawie w 1882 roku znajdujemy taki oto opis miejscowości: "Kamionna (z Pasierbcem), wieś, pow. bocheński, w położeniu pagórkowatem, 389 m. n. p. m. przypiera lasami rozłożonemi na wzgórzach dochodzących 669 m. wys. do gościńca bocheńsko-sądeckiego. Wieś rozrzucona, dlatego jej części noszą nazwy: Cerkówka, Rakówka, Podlasiska, Spancerówka i Bródek.
     Przysiółek Pasierbice leży na południe od wsi, śród lasów u stóp Pasierbieckiej góry,789 m wysokiej. Kamionna ma 1200 mk. rzkat, 110 dm, młyn wodny, tartak. Należy do parafii rzym-kat. w Trzcianie, a urzędu pocztowego w Wiśniczu, skąd oddalenie wynosi 4 kil.  Mniejsza posiadłość ma obszaru 150 mr. roli i łąk a 600 mr. lasu; posiadłość większa 773mr roli 185 mr łąk, 182 mr. pastw. i 358 mr lasu. Długosz (Lil.benef 11,178) zowią ją K.al. 0ssykowa i wymienia jako własność Urbana Łapki h. Drużyna. Wieś ta należała dawniej do dóbr duchownych, została przez rząd austryacki skonfiskowana Jezuitom w r. 1816. Jest obecnie własnością Józefa Kościeszy Ożegalskiego. Podanie niesie, że Lubomirski pobił w Kamionnej Szwedów w drodze z Krakowa do Sącza, dotąd po polach znajdują się szczątki oręża".
     W 1928 roku jego obszar majątku Ożegalskich wynosił 272 ha. Wybudowali oni w centrum wsi dworek i piękny park. Po śmierci Józefa Ignacego Ożegalskiego współwłaścicielami majątku zostali jego synowie: Franciszek i Stanisław.
     Stanisław Ożegalski został przez Niemców za ukrywanie uciekinierów z niemieckiego obozu aresztowany i w 1942 roku zamordowany w Oświęcimiu.  Aż do parcelacji majątku w 1945 roku był jeden właściciel majątku - Franciszek, bo Stanisław zmarł bezpotomnie. Majątek ten został rozparcelowany pomiędzy tutejszych chłopów. Część, w tym las, stała się własnością Nadleśnictwa w Brzesku.
     Z kolei "Książka Adresowa Polski" z roku 1929 podaje następujące dane o Kamionnej: "Wieś i gmina, pow. Bochnia, sąd pow. Wiśnicz, sąd okr. Kraków, 906 mieszk. kolej (11 km) Tymbark, poczta Trzciana, Telegraf: Rzegocina, Telefon: Łapanów. Właściciele ziemscy: Oregalski Józef (272). Młyny: Hojda J. (Wod), Piwo: Chylak T. - Gottlob J. Różene towary: Dudziak Jan - Fodergrűn I. - Korn Ch. - Surma Jan. Tartaki: Dudziak Jan. Tytoniowe wyroby: Korda Fr.".
     W czasie II wojny światowej miejscowa ludność była przymusowo wywożona do obozu pracy w Kłaju. W okolicy doszło do kilku drobnych starć pomiędzy partyzantami mającymi obóz na szczycie Góry Kamionnej, a oddziałami niemieckimi stacjonującymi w niedalekiej Leszczynie.
     Po wojnie Kamionna rozwijała się, chociaż przebiegało to dosyć powoli. W czerwcu 1956 roku otwarto linię autobusową, łączącą Kamionną z oddalonym o 45 km Krakowem.  W tym też roku Kamionna stała się siedzibą Gromadzkiej Rady Narodowej i była nią do 1962 roku, kiedy to Kamionna weszła w skład Gminy Trzciana. W 1957 r. uruchomiono tu Szkołę Przysposobienia Rolniczego. W 1960 r. dzięki staraniom mieszkańców i ówczesnego sołtysa Alojzego Dudziaka nastąpiła elektryfikacja wsi. W 1962 r. zaczął kursować regularnie autobus z Bochni. Kwatera kierowcy znajdowała się u Floriana Stafińskiego.
    W dniu 11 sierpnia 1963 roku w Kamionnej odbyłą się duża uroczystość patriotyczna, związana z odsłonięciem odrestaurowanej Kolumny Szewdzkiej, posadowionej na miejscu walki Polaków z najeźdźcami ze Szewcji podczas tzw. "Potopu" w 1656 roku.
    Na początku lat 70-tych wybudowano most na potoku Przeginia, umożliwiając m.in. łatwiejsze dojście do kościoła mieszkańcom z południowo-wschodniej części wsi. Równocześnie zmodernizowano drogę. W roku 1984 wybudowano wodociąg, pozostałe z inwestycji pieniądze przeznaczono na zakup rur do gazociągu, który przeprowadzono w 1986 r. Z dniem 1 stycznia 1995 roku Kamionna, po odłączeniu się od gminy Żegocina, stała się jedną z siedmiu sołectw nowej gminy w Trzcianie. Największą inwestycją we wsi na przełomie XX i XXI wieku stała się budowa nowej szkoły, którą oddano do użytku w końcu 2002 roku.
     W roku 2009 rozpoczęła się duża inwestycja - wodociągowanie wsi. W Kamionnej zbudowano ujęcie wody i zbiornik wyrównawczy, Na początku 2011 roku przekazano do użytku nową salę gimnastyczną, dobudowaną do budynku szkolnego. Inwestycja w dużej częsci została sfinansowana ze środków Unii Europejskiej. Zrealizowana została także duża inwestycja drogowa. W przysiółku Czarne Błota wybudowano estakadowy most na drodze powiatowej Leszczyna - Nowe Rybie.  Pięcioprzęsłowy most ułatwia komunikację pomiędzy powiatem bocheńskim, a limanowskim.