Usytuowane na górzystym cyplu miasto Czerwonogród leży w środku kotliny, której stoki dominują nad zamkiem. Położone jest nad rzeką Sołokiją, która przecina kotlinę, otaczając wzgórze i wpadając do Dniestru. Miasto leży w obwodzie lwowskim, 15 km na wschód od granicy z Polską i jest stolicą rejonu czerwonogrodzkiego.  

Miasto przechodziło przez różne ręce – , należało do książąt ruskich i litewskich czy hospodara mołdawskiego. Zdobyte zostało przez Kazimierza Wielkiego, stało się własnością Władysława Jagiełły, który nadał je Spytkowi z Melsztyna. Później przeszło w ręce Wielkich Książąt – Świdrygiełły i Witolda. W 1434 roku, wraz z włączeniem Podola do Korony, Czerwonogród uzyskał status miasta królewskiego i stał się siedzibą starostwa niegrodowego. Jako pierwszy ten urząd pełnił kasztelan kamieniecki – Teodoryk Jazłowiecki-Buczacki (zm. 1456). Zamek wzniesiono z miejscowego czerwonego piaskowca, stąd nazwa miejscowości. Dokładna data powstania oraz wygląd najstarszego zamku nie są znane. Jednakże ze źródeł XVII-wiecznych wynika, że ówczesny murowany zamek miał kształt czworoboku z czterema okrągłymi basztami na narożach, otoczony zewnętrzną linią murów.  

Jako Krystynopol – miasto założone w rozgałęzieniu dwóch rzek: Sołoki i Bugu przez wojewodę krakowskiego i hetmana polnego koronnego – Szczęsnego Kazimierza Potockiego, istnieje od 1692 roku. Nazwa pochodzi od imienia jego żony, Krystyny z Lubomirskich, którą poślubił w 1661 roku. W 1695 roku ufundował w mieście klasztor bernardynom i kościół pw. Św. Ducha, tam też spoczął po śmierci w 1702 roku. Wojewoda kijowski i wołyński Franciszek Salezy Potocki, prawnuk hetmana, obrał sobie Krystynopol za siedzibę i w miejscu dawnego pałacu wystawił nową, wspaniałą rezydencję, budowaną w latach 1756–1762 według projektu znanego architekta Pierre’a Ricauda de Tirregaille’a (1725-1772). Ściśle łączyła się ona z miasteczkiem, gdyż bezpośrednio z rynku wjeżdżano na pierwszy dziedziniec, mijając po lewej stronie oranżerię z ogrodem kwiatowym. Tak opisał to Józef Ignacy Kraszewski w Starościnie bełskiej: 

„Naprzeciw pałacu wielkiego i rozległego, o dwóch obszernych podwórcach z oficynami, mnóstwem zabudowali pomniejszych i wspaniałą bramą wjazdową wśród rozłożystego i cienistego parku, stał hauptwach [wartownia – przyp. ABR] zajmowany przez leibgwardyą dragonów, która przy każdem ukazaniu się wjeździe lub wyjeździe wojewody, biła w bębny, występowała i oddawała mu honory wojskowe. Obywatel lub urzędnik wojewódzki, mimo tytułu pana brata, który im dawano na kopercie, nie śmieli zajechać przed pałac w Krystynopolu. Przez uszanowanie wysiadali w bramie z karet i powozów i pieszo szli do drzwi pałacowych. Żołnierze w bramie straż trzymający, nie puściliby powozu; jedne tylko damy miały pozwolenie zajeżdżać przed pałac, ale powóz natychmiast nazad za bramę wychodził.”  

W głębi za budynkiem bramnym znajdował się dziedziniec drugi o parterowych, wąskich skrzydłach łączących krańce budynku bramnego z pałacem w zamkniętą przestrzeń. W środkowej części korpusu znajdował się ryzalit o zaokrąglonych narożnikach. Rezydencja była wspaniała, wnętrza niezwykle bogate, a od strony południowej założono rozległy park o kształcie regularnego prostokąta w stylu włosko-francuskim, na którego osi ulokowano w jednym rzędzie trzy partery kwiatowe o kształcie czworoboków z dwiema fontannami. Między nimi rozmieszczono altany, zaś w dalszej części parku urządzono sieć sadzawek i kanałów. Była to godna siedziba dla Franciszka Salezego Potockiego nazywanego „małym królem na Rusi” – jednego z najpotężniejszych i bezdyskusyjnie najzamożniejszego magnata Rzeczpospolitej. Pod jego rządami dwór nie ustępował w niczym dworom królewskim, nawet etykieta wzorowana była na dworze królewskim. Jak czytamy w pamiętnikach oficjalisty Potockiego, Antoniego Chrząszczewskiego: 

„Przedniejsza służba Salezego Potockiego, oprócz pokojowców z niedorosłej szlachty, szatnych, łowczych, podczaszych, koniuszych itd. składała się z 30 dworzan […]. Milicyą nadworną formowała piechota, dragonia, ułani i kozacy. Oficerowie regularnego wojska byli patentowani od Króla i nosili foldcechy wojska narodowego”. 

Niezwykle surowo strzegła etykiety wojewodzina Anna Elżbieta Potocka, która pewnego razu „potężny wycięła policzek” nowemu dworzaninowi za to, że podtrzymał ją pod ramieniem przy wsiadaniu do powozu, zamiast zgodnie z etykietą podać jedynie łokieć do wsparcia.  

Gdy Potoccy wydawali córkę, Marię Klementynę za Alojzego Fryderyka, syna hrabiego Henryka Brühla, potężnego ministra króla Augusta III, wesele w krystynopolskim pałacu odbyło się z iście królewską pompą. Opisał je Kraszewski w Starościnie bełskiej: 

„Wesele, które się także w rezydencyi wojewodów odbyło, niemniéj było wystawne i wspaniałe; zaproszeni na nie zostali wszyscy posłowie dworów zagranicznych, ministrowie, wielu biskupów, wojewodów, książąt, przyjaznych domowi Brühlów i Potockich. […] Od pałacu do kościoła OO. Bernardynów, cała ulica wysłana była suknem czerwoném, którędy nowożeńcy i dostojni goście szli do ślubu. Zbytek i okazałość były tak wielkie, że koszta weselne obrachowywano naówczas na 253,000 złotych. Dla jednego fajerwerku, który dnia tego miał być spalony na cześć młodéj pary, sprowadzono umyślnie z Warszawy P.C.G. Deybel'a de Hameran, porucznika i adjutanta artylleryi koronnéj, najbieglejszego pyrotechnika owego czasu. On urządzał wielki dramat ognisty, którego szczegóły pozostały nam w planie własną jego ręką skreślonym. Prolog jego stanowił wystrzał z dział dwunastu; praeludium trąby i kotły grzmiące. W akcie pierwszym na lewém skrzydle ukazywała się cyfra M. P. (Marya Potocka), w białym ogniu uwieńczona koroną; na prawém F. B. (Fryderyk Brühl), równie jaśniejąca i ukoronowana. Między cyframi dwanaście fontan wyrzucało krople iskrzące, a powyżéj Opatrzność w symbolicznym czuwała trójkącie. Akt II i III niewiele się różnił zresztą od pierwszego; spalono niesłychaną ilość rac à la ferte, szmermelów, bukiet à la girandola, kaskad i. t. p. W ostatku ogromne zabłysło: Vivant! wśród błękitnych ogniów, znowu Opatrzność nad niém, a wkoło kaskady, bukiety, fontanny, girandole, ogniotryski à la ronde.  
Wiele się tak pieniędzy wyrzuciło z ogniami na tém weselu, wiele spaliło prochu, wiele wypiło wina; ale wojewoda po książęcemu, po królewsku, jak mówiono, wystąpił; gadała o tém cała Polska i gazetki latały po kraju.” 

Pałac podupadł po śmierci hetmana w 1772 roku, gdy jego syn – targowiczanin, Stanisław Szczęsny Potocki przeniósł się do Tulczyna. Być może wpływ na porzucenie domu rodzinnego miała tragedia, jakiej doświadczył w młodości. Z pałacem Potockich w Krystynopolu wiąże się bowiem jedna z najsmutniejszych historii miłosnych i równocześnie jeden z najbardziej szokujących skandali obyczajowych w XVIII-wiecznej Polsce. Antoni Malczewski napisał w 1824 roku słynny poemat Maria, oparty na tej historii. 18-letni wówczas Stanisław Szczęsny Potocki zakochał się w Gertrudzie Komorowskiej, wywodzącej się ze starego szlacheckiego rodu, niestety niezbyt zamożnego. Młodzi pobrali się w obrządku grekokatolickim 16 grudnia 1770 roku, wprawdzie z błogosławieństwem rodziców panny, ale bez wiedzy Potockich, którym zdecydowanie nie odpowiadała taka synowa. Na polecenie Franciszka Salezego Potockiego ciężarną już wówczas Gertrudę porwano z zamiarem osadzenia w klasztorze, a że po drodze wskutek wypadku, zaniedbania, a może i celowego działania zmarła – ciało ukryto, by zatuszować zbrodnię. Józef Białynia-Hołodecki w lipcu 1905 odkrył razem z Aleksandrem Czołowskim grobowiec Gertrudy Potockiej w podziemiach kościoła w Witkowie, a rok później wydał publikację temu poświęconą. Tak pisał o tragicznym losie niegodnej domu Potockich synowej: 

„Porwana, wleczona, maltretowana, duszona, Gertruda poroniła i skonała w rękach oprawców. […] Wiedzieli dobrze przewódcy wyprawy, co mają czynić z żywę Szczęsnową Potocką, potracili atoli głowy na widok martwego ciała. Przerażeni zbrodnią, nie wiedzieli, co począć z zwłokami, z tem martwem, a przecież tak żywem świadectwem spełnionej zbrodni […]. Po naradzie, postanowili zatopić ciało w najbliższej wodzie i zatrzeć ślady występku.” 

Ciało odnaleziono wiosną, gdy puściły lody i zbrodnia wyszła na jaw. Wtedy Potoccy użyli swojej fortuny, aby skandal wyciszyć: „Komorowscy po utracie córki żałośni udali się do Lwowa i rozpoczęli proces, ale im brakowało dowodów obwiniających Potockich. Hrabia Komorowski […] nie mógł się spodziewać wygranej, bo nie miał żadnych pewnych dowodów; a wojewoda [tzn. Potocki – przyp. ABR] sypał pieniędzmi na swe uniewinnienie.” Tymczasem zrozpaczony Szczęsny najpierw usiłował popełnić samobójstwo, a następnie wyjechał za granicę, skąd wrócił dopiero po śmierci ojca. Wówczas oddał znajdujący się w granicach zaboru austriackiego zadłużony Krystynopol i okoliczne włości księciu Adamowi Ponińskiemu jedynie pod warunkiem spłacenia ciążących na nim długów, a sam przeniósł się do Tulczyna. Mury pałacowe były wówczas zrujnowane, toteż gdy właścicielem miasta został syn Adama, Karol Poniński, około 1820 r. rozebrał dwie baszty i trzy boki założenia zamkowego. Pozostałe dwie baszty i mury z nimi związane włączono do nowego pałacu klasycystycznego. Syn Karola, Kalikst, kontynuował renowację pałacu, a przebudową w stylu neogotyckim kierował Fryderyk Baum. Stare baszty zostały rozebrane do fundamentów i na ich miejscu zbudowano nowe, z oknami w stylu neogotyckim i attykami na szczycie. Baszty te akcentowały wschodnią elewację dwutraktowego pałacowego korpusu z kolumnowym portykiem i tarasem zbudowanym prawdopodobnie w miejscu dawnego zamku. O wykorzystaniu starych murów zamkowych mogą świadczyć zarówno nieregularność planu, jak i różna grubość ścian pałacowych. Frontową elewację zachodnią zdobił trójosiowy pseudoryzalit z trójkątnym przyczółkiem i wspartym na kolumnach balkonem nad głównym wejściem. Wokół pałacu roztaczał się park z fontanną i altaną widokową. 

Po śmierci Kaliksta Ponińskiego pałac przeszedł w ręce Lubomirskich. Ostatnią właścicielką była Maria Eleonora z Zamojskich Lubomirska (1862-1945). Na przełomie XIX i XX w. miały miejsce prace budowlane prowadzone przez Kazimierza Mokłowskiego. Pałac utrzymywany starannie do I wojny światowej, zdewastowany przemarszami wojsk w latach 1914-1920, remontowano w międzywojniu, lecz remontu nie ukończono przed wybuchem II wojny światowej. Ostatnim właścicielem przed wojną był płk Zygmunt Lipiński, który przekazał majątek władzom powiatowym. Pałac został częściowo wyremontowany, mieści aktualnie oddział lwowskiego Muzeum Historii Religii. Niestety nie zachował się park pałacowy – na tym terenie mieści się obecnie m.in. stadion piłkarski.