Колись, століття тому, місто потерпало від... власного географічного розташування. Начебто місце для поселення вибрали жителі непогано, оселившись на невеликому острові між двома рукавами Південного Бугу. Навіть ім'я місту дали завдяки цьому острову: за легендою, був він спочатку вкритий лозою та калинами, по яким вився хміль. Та всього в 6 кілометрах від Хмільника пролягав сумнозвісний Чорний шлях, яким щороку рухалися з безкрайніх степів Півдня орди татаро-монголів: палити та руйнувати подільські поселення, гнати в ясир тисячі полонених. Конче потрібен був замок. І він з'явився.
Важко дізнатися, яким він був спершу, адже стратегічне розташування замку змушувало володарів міста постійно його укріплювати та розширювати. Відомо, що в останній період князювання Вітовта фортеця була значно посилена. На те були сумні причини: литовсько-руська армія була розбита на Ворсклі кримчаками у 1399 році. Поразка потягла за собою зміну кордонів: володіння Вітовта у Причорномор'ї були втрачені. Хмільник стає прикордонним містом. Князь не міг не розуміти важливість укріплення прикордонних замків в цілому і Хмільницького зокрема.
В роки боротьби за литовський великокнязівський трон між Свидригайлом і Сигізмундом Хмільник став власністю князя Федора Корибута Несвицького, союзника Свидригайла. Та після присяги князя Несвицького польському королю хмельницький замок в 1434 році відійшов до Польщі. Місто стало центром хмільницького староства в щойно утвореному Подільському воєводстві. Польські хроністи відмічали, що замок на той час був сильним, а житлові будинки розміщувалися навколо фортеці. Фактично, це перший більш-менш докладний опис споруди у хроніках.
Литовці не примирились з втратою важливого форт-посту і до 1447 року продовжували вважати Хмільник своїм містом, при цьому не роблячи ніяких реальних кроків щодо повернення міста. Князі обмежилися ностальгією.

За турками знову повернулись поляки, а за століття місто увійшло до складу Російської імперії. Не дивлячись на появу сякої-такої промисловості (поташна фабрика, селітровий та скляний заводи), місто ледь животіло. Замок, втративши стратегічне значення, поступово руйнувався. Дерев'яні хатини (а такі були майже всі, крім трьох будинків у центрі) вздовж річки щовесни заливали повені, восени дороги перетворювались на непрохідне болото, літо приносило з собою часті пожежі. Так, 1834 року згоріло відразу 113 будинків. На фоні загального зубожіння виділялися у місті лише церкви. З 1788 по 1910 роки у місті було споруджено 4 православних храми.

Та найцікавіша споруда Хмільника виросла у 1911-1915 роках поблизу старих замкових мурів. Тут, на пагорбі над Бугом, за проектом відомого архітектора І.О.Фоміна зводиться розкішний палац графа Костянтина Івановича Ксідо (граф воював, а ще видавав книги по географії). З боку річки відкривається панорама ренесансного замку з баштами у кутках, а от парадний фасад будівлі з колонадою над головним входом - взірець архітектури класицизму. Як пише в своїй статті російський дослідник Володимир Сєдов, "В маєтку Хмільник Фомін скорочує простір неопаладіанської класики і збільшує простір нестримної, могутньої, хтонічної неокласики". Арковий міст до палацу теж спланував І.Фомін у 1915 р. (проект не був повністю втілений у життя).

Ох і цікава історія з цим Ксідо: був він красенем, та без грошей. Обміняти зовнішність на обручку багатійки чорнявому греку порадив... великий російський письменник Іван Бунін, який у ті роки служив неподалік, у Летичеві. Ксідо послухався — і одружився на глухонімій і не надто молодій графині Катерині Володимирівні Левашовій. Головною її принадою були титул, а також 28 сіл й чималі грошові активи. Мешкав Ксідо, щоправда, переважно в Петербурзі, воював у Першу світову, а після революції Костянтин із дружиною емігрував на Захід — як і переважна більшість російських аристократів. Кажуть, повернувся у Хмільник у 1943 р., поблукав своїм палацом, зустрів колишнього лакея Дмитра — і повернувся на нову батьківщину, начебто в Чехію. Маєток у післяреволюційні роки використовувався під навчальний заклад, потім його окупував НКВС, а в Другу світову тут були звичайні склади. В 1964 р. у замку відкрився готель, а у вежі — громадський краєзнавчий музей.

Відчути себе графами гостям готелю важко: зі зручностей тут лише електрика та вентилятор. А в колишній бальній залі взагалі сушать білизну. В 2006 році міська влада вирішила здати замок (чи то пак готель) в оренду, та претенденти на звання вельмож, які прибували з Києва і навіть Австрії, так і не ризикнули. Хоча якийсь португалець і обіцяє звести під Хмільником п’ятизірковий готель.