W miejscu, gdzie obecnie leży miasto Grybów, od niepamiętnych czasów, krzyżowały się dwa ważne szlaki handlowe: jeden z zachodu Europy na wschód – na Ruś Czerwoną; drugi z nad Bałtyku na Bałkany. Przy tego rodzaju drogach handlowych powstawały osady, wioski i miasta.

Tereny na południe od Grybowa aż do granic Królestwa Polskiego były zalesione, głuche i dzikie. Strach było tutaj się poruszać tak z powodu dzikich zwierząt, jak i częstych napadów na karawany kupieckie przez bandy rozbójników węgierskich.

Legenda mówi, że król Władysław Łokietek ofiarował ziemianinowi grybowskiemu Grzybowi za szczególne zasługi włożone w bitwę pod Płowcami ziemie położone na południe od – będącego wtedy tylko małą osadą – miasta Grybowa. Król pragnął, aby Grzyb położył kres zbójectwu, które miało tam często miejsce i aby dzięki temu w tamtym miejscu został zapewniony spokojny przejazd karawanom kupieckim szlakiem handlowym wzdłuż rzeki Białej. Zbójnicy jednak w niedługim czasie zamordowali Grzyba oraz jego dwóch synów – Floriana i Wawrzyńca. Na pamiątkę obu młodzieńców założone tutaj przez polskich osadników wsie nazwano Flornikową i Wolą Wawrzkowską. Nazwy te z biegiem czasu uległy zmianie na Florynkę i Wawrzkę. W XIV wieku opróczy Grybowa powstały także wsie: Brunary, Bińczarowa i Berest.

Mimo braku dokumentów historycznych, należy przyjąć, że początek Florynki przypada na XIV wiek. Jako zorganizowana wioska wołoska jest wymieniona po raz pierwszy w 1529 roku. Spotyka się dużo czysto polskich nazwisk, demograficznie silniejsi byli jednak Wołosi i dlatego też Florynka rozwinęła się jako wioska łemkowska. Wołochów bowiem od XIX wieku zaczęto nazywać Łemkami, a zamieszkałe przez nich wsie Łemkowszczyzną.

Łemkowszczyzna ciągnęła się pasem przygranicznym polsko-słowackim od górnego biegu rzeki San aż po rzekę Poprad. Łemkowie byli „ruskimi góralami”. Na co dzień posługiwali się dialektem języka ukraińskiego, ubierali się w swoje regionalne stroje ludowe i byli wyznania prawosławnego oraz greko-katolickiego, zwanego inaczej unickim.

Jako wioska wołoska, Florynka była oficjalnie założona 27. września 1574 roku przez biskupa krakowskiego Franciszka Krasińskiego, chociaż istniała już o wiele wcześniej i należała do dóbr ziemskich biskupów krakowskich skupionych w tzw. Kluczu Muszyńskim. Florynkę nazywano w Muszynie – Flornikową, Florencją, Florentką, a od 1683 roku Florynką biskupią. Ludność wołoska była pierwotnie wyznania prawosławnego. Nawet w bardzo małych wioskach sama tworzyła sobie parafie prawosławne. Tak było i z Florynką. Dopiero dzięki Unii Brzeskiej (1595) i zabiegom biskupa krakowskiego Marcina Szyszkowskiego, Florynka wraz z okolicznymi prawosławnymi parafiami przyjęła obrządek greko-katolicki ok. 1620 roku i została erygowana tu przez tegoż biskupa parafia greko-katolicka.

W XVII wieku Florynka była w tej okolicy jedną z większych wsi. W 1780 mieszkało w niej 100 rodzin. Posiadała własną szkołę parafialną. W 1785 roku została wybudowana nowa cerkiew z kamienia, gdyż dotychczasowa drewniana pod wezwaniem św. Michała była już bardzo zniszczona przez czas i nie mieściła wszystkich tutejszych ludzi. Przy budowie nowej cerkwi pracowali murarze włoscy, którzy także w tym czasie budowali mosty i wiadukty pod linię kolejową Tarnów – Nowy Sącz – Muszyna – Koszyce. Budowa cerkwi trwała prawie trzy lata. Przygotowania do tej budowy poczynili prawdopodobnie dwaj po sobie następujący uniccy proboszczowie: Atanazy Czermiański i Justyn Konstantynowicz. Natomiast następny z kolei proboszcz Michał Rydzaj, wymieniony na nagrobku przy kościele jako jego budowniczy, dokończył pracę swych poprzedników, bo parafię tę objął w 1874 roku. We Florynce mieszkało wtedy przeszło 900 ludzi i wszyscy – z wyjątkiem kilku rodzin polskich i żydowskich – byli wyznania greko-katolickiego.

5 grudnia 1918 roku z inicjatywy kilku działaczy łemkowskich proklamowano we Florynce Ruską Narodową Republikę Łemków. Władza „rządu” rozciągała się na kilkadziesiąt łemkowskich wsi w powiatach nowosądeckim i gorlickim. Po 16-tu miesiącach władze powiatowe aresztowały działaczy i „rząd”, kładąc tym samym kres republice.

W latach 1935-36 we Florynce mieszkał 1260 osób: 265 greko-katolików, 905 osób prawosławnych, 16 rzymsko-katolików i 28 Żydów. 14 lipca 1945 roku wskutek agitacji przysłanych tu z ZSRR agentów NKWD wyjechało na Ukrainę około 60 rodzin łemkowskich. Pozostała ludność łemkowska Florynki została 29 czerwca 1947 roku przymusowo wysiedlona na Odzyskane Ziemie. Została tylko jedna rodzina i kilkanaście osób spokrewnionych. Do opuszczonych domów bardzo szybko napłynęła ludność polska z okolicznych przeludnionych wiosek. 28 sierpnia 1946 roku przybył do Florynki pierwszy rzymsko-katolicki duszpasterz – ks. Michał Żurek. Niecałe 2 lata później przybyły z Tarnowa 3 siostry Józefitki i zamieszkały w opuszczonym przez prawosławnego proboszcza domu, w którym do dzisiaj mieszkają. Siostry prowadzą przedszkole dla dzieci oraz pełnią posługę przy parafii.

5 kwietnia 1949 roku duszpasterstwo Florynki objęli Księża Najświętszego Serca Jezusowego, nazywani powszechnie Sercanami. Pierwszym duszpasterzem był ks. Stanisław Sidełko SCJ. Dnia 29 grudnia 1951 roku została zniesiona parafia unicka i erygowana rzymsko-katolicka. Dekretem z 6 maja 1969 r. Ksiądz Biskup Jerzy Ablewicz Ordynariusz Tarnowski ustanowił patronów świątyni: Najświętsze Serce Pana Jezusa i św. Michała Archanioła. Tym samym dał możliwość dwukrotnego zyskiwania przez wiernych odpustu zupełnego z okazji parafialnego święta.

Kościół jest bezstylowy, o nikłych cechach klasycyzmu i budownictwa cerkiewnego, z kamienia, otynkowany i pokryty blachą. Jednonawowy, o nawie wydłużonej i nieznacznie poszerzonej w części środkowej. W poszerzonej nawie są malowidła przedstawiające postacie mające wielki wpływ na rozwój chrześcijaństwa: św. Piotra, św. Pawła, św. Helenę wraz z synem Konstantynem a także św. Cyryla i Metodego. Poniżej zawieszone są stacje Drogi krzyżowej wykonane z kolorowanego miedziorytu. 

Prezbiterium jest prostokątne, a w nim od 1973 roku nowy posoborowy ołtarz. Bezpośrednio za nim duży obraz Serca Jezusowego namalowany przez Adolfa Kazimierza Hyłę w 1949 roku (autora najbardziej znanego wizerunku Jezusa Miłosiernego), za którym na ścianie umieszczony jest późnoklasyczny ikonostas z 1875 roku. W poszerzonej nawie umieszczone są dwa późnobarokowe ołtarze z początku XVIII wieku. W prawym obraz Chrystusa ukrzyżowanego z końca XVIII wieku przedstawienie Chrztu Chrystusa w Jordanie. W lewym Matki Bożej nad nim obraz Pana Jezusa w Ogrójcu.

Na płaskim stropie są obrazy: koronacji Matki Bożej, Przemienienia Pańskiego, Narodzenia Pana Jezusa i gołębicy - symbolizującej Ducha Św.  Malowane na deskach z okresu budowy kościoła.