Точна дата заснування міста Хмельницького невідома, однак достовірно можна стверджувати про існування Плоскирова (Плоскировець) вже у першій половині XV ст. На той час Поділля стає ареною боротьби між литовськими князями та Польським королівством, яка закінчилася на користь останнього. У 1431-1434 роках територія Західного Поділля, включаючи верхнє Побужжя, відійшла під владу Корони Польської.

1434 року у Західному Поділлі було запроваджено польський адміністративно-територіальний устрій і утворено Подільське воєводство (адміністративний центр – місто Кам'янець), яке складалося з Кам'янецького, Летичівського і Червоногородського повітів. Східне Поділля ще на деякий час залишилось у складі Великого князівства Литовського.

Польський король Владислав ІІ Ягайло в ці роки надає своїй шляхті привілеї на новоприєднані подільські володіння. Серед населених пунктів, що згадуються у документах королівської канцелярії, знаходимо поселення сільського типу (villa) під назвою Ploskirоwcze (Плоскирівці) та відповідний запис: 10 лютого 1431 р. у місті Сопоті король Владислав ІІ Ягайло записує Янові Чанстуловському 100 гривень на володіння ”селами Голисин та Плоскирівці на річці Бог у Летичівському повіті Подільської землі” («… super villis Holissin et Ploskirоwcze super fluvio Boh iacentu in terra Podoliensi et districtum Latichoviensi sitas»). В роки королювання  Владислава ІІІ (1434-1444рр.) право на володіння поселенням підтверджується, однак поселення вже названо Ploskirоw – Плоскирів.

Цю найдавнішу на сьогодні писемну згадку про Хмельницький виявив у Варшавському архіві давніх актів історик Віталій Михайловський.