Legenda głosi, że początki wsi sięgają panowania króla Kazimierza Wielkiego (1333-1370). Wędrując po górach, zmęczony długą drogą, król usiadł w cieniu drzew. Odpoczynek był tak przyjemny, że król nazwał to miejsce Cieniawa. Również w naukowych opracowaniach, np. Eugeniusza Pawłowskiego - wybitnego znawcy nazw miejscowych Sądecczyzny i Zdzisława Stiebera - pochodzenie nazwy Cieniawa wyprowadzane jest od ukształtowania terenu i szaty roślinnej. Może więc znaczyć tyle co cienista - prawdopodobnie w chwili zakładania Cieniawy było dużo drzew rzucających cień. Natomiast według Jana Długosza - pisze o tym w swojej Historii Polski - nazwa pochodzi od ściętego lasu. Na dowód Długosz przytacza nazwę śląskiej miejscowości Ścinawa - którą po polsku tłumaczy się właśnie Cieniawa.
Historia powstania wsi:Nie wiadomo kiedy dokładnie została założona wieś. Istnieje kilka dokumentów lokacyjnych, które podają różne daty powstania Cieniawy - 1364, 1416 i 1464. Można przypuszczać, ze powstanie wsi nie było aktem jednorazowym, ale odbywało się stopniowo, aż do 1464 roku, kiedy to z całą pewnością Cieniawa już istniała jako samodzielna wieś. O prastarym pochodzeniu miejscowości może świadczyć również fakt, że domy są rozrzucone po dolinach i zboczach wzgórz, można więc przypuszczać, że wieś powstała w wyniku swobodnej, dzikiej kolonizacji. Ten "rozproszony" typ wsi jest charakterystyczny dla najstarszych miejscowości na Sądecczyźnie. Dziś Cieniawa składa się z kilkunastu osiedli - przysiółków, które tradycyjnie nazywane są w zależności od usytuowania w terenie, nazwiska rodziny bądź zawodu, jaki wykonują mieszkańcy przysiółka.
Historia Cieniawy od początku jest ściśle związana z sąsiednim Mystkowem, który przez ponad 500 lat był siedzibą parafii. Cieniawa usamodzielniła się jako parafia dopiero w latach 80-tych XX wieku. W 1980 roku Kuria Diecezjalna zaleciła odprawianie w każdą niedzielę jednej mszy świętej w Cieniawie. Uruchomiono pierwszą kaplicę - początkowo w salce katechetycznej w domu prywatnym, potem w wyremontowanym i dostosowanym do potrzeb dawnym Domu Nauczyciela. Pierwsza pasterka w kaplicy została odprawiona w Boże Narodzenie na przełomie lat 1980/1981. W 1981 roku po uzyskaniu zezwolenia od władz państwowych, wybudowana została nowa kaplica, a w 4 czerwca tego roku Kuria Diecezjalna wyznaczyła księdza Franciszka Olczaka na duszpasterza parafii. Jako proboszcz podjął trud budowy kościoła, który stanął w ?. Opiekę nad parafią sprawuje do dziś.
Ważne daty w historii Cieniawy: