Наймирніше місто в усі часи не могло існувати без надійного захисту, сильного війська і волелюбного населення. А що вже казати про невелике містечко буферної для Європи Київської Русі з полчищами східної орди і кримських татар у вигляді «добрих», завжди готових за невмінням створювати відняти, розорити знищити сусідів.
У ті далекі часи, коли українські землі були незалежні і сильні, головною зброєю селища на річці Мирці, за добру вдачу місцевих жителів прозваного Мирів, були високі земляні вали, що п’яти з половиною кілометровим кільцем огороджували його від непроханих гостей. Та тільки миролюбність хоч і за підтримки стін десяти метрів заввишки – поганий помічник у війні – його, як і багатьох побратимів по нещастю, стерли з лиця землі незліченні Батиєві орди.
Після розорення люди в урочищі Великі вали більше не повернулися, заснувавши нове поселення під прапором литовського великого князя Ольгерда в 1331 році вище за течією Усті, яке не довго мудруючи для власної ідентифікації підкреслено було названо Немировом.
Згідно ж іншої легенди мировці, котрі взяли собі ім’я від річки, на якій колись укладено мир між княжою дружиною і печенігами, мали не стільки добру вдачу, скільки безстрашну волю до свободи й непокори будь-яким гнобителям. Так що коли східні орди татаро-монгол підступили до захисних волів і запропонували мир в обмін на здачу без опору, відважні жителі Мирова вибрали «не мир». Їх селище було знищено, а нове вище за течією Мірки стало гордо іменуватися Немировом у пам’ять про предків, які обрали свободу ціною жертви своїм домом, своїм добробутом, своїм життям.
А ще існує думка, що сучасне місто стоїть на місці, де в дпвнину українські війська оточили татарський загін, і на всі благання кочівників про пощаду прозвучало гордо-презирливе російське «не мир», яке лягло в семантичну основу нового імені поселення. Хоча можливо теорія про володіння цією землею в XIV столітті литовським підданим Нмирею теж має своє право на існування.
І хоча безліч легенд і покрив таємниці над часом заснування Немирова дає простір для фантазій і домислів, згідно офіційних збережених хронік історія датує його 1506 роком, коли він вперше згаданий в ярлику кримського хана Менглі-Гірея.