Современное поселение в устье Кальмиуса основано в XVI веке запорожскими казаками, потомками бывших бродников, как сторожевой пост Домаха (Кальмиус) для защиты зимовников, промыслов и путей сообщения от нападений крымских татар, которые после вторжения в 1475 году туда турецких войск стали вассалами Османской (Оттоманской) империи.
Историк А. М. Черногор называет более точную дату основания Домахи — 1500 год. Это происходило во времена интенсивного создания турками своих крепостей на побережье Чёрного и Азовского морей: Аккерман, Очаков, Кизыркермен (на Днепре ниже порогов), Азов (в устье Дона). А казаки жили в непосредственной близости с десятками тысяч кочующих ногайцев, переселившимися из Заволжья и ставшие частью населения Крымского ханства.
Возникновение казачества на Украине относится к 80-90-х годам XV века, когда в Киевской и Подольской губерниях появились отряды казаков — «свободных людей», занимающихся охотой, рыбной ловлей, бортничеством. На рубеже 70-80-х годов XVI века разрозненные казаки стали объединяться в «сечи» (или «городки»), оформившиеся позже в военно-политическую организацию — Запорожская Сечь, центром которой служило наиболее укреплённое место пребывания коша (центрального органа управления войском) — Запорожская Сечь. Во времена существования Новой Сечи (1734 — 1775 годы) территорию Запорожья разделили на паланки (округа): сначала 5 (Ингульская, или Перевезская, Бугогардовская, Кодацкая, Самарская и Кальмиусская паланки), позже — 8 (добавились Прогноинская, Орельская и Протовчанская паланки).
Расширение рыбного промысла на берегах Азовского моря вызвало появление казацких зимовников. Зимовник — довольно большое хозяйство казаков из числа постаревших влиятельных запорожцев, старшин. Согласно «Истории» Д. И. Яворницкого, в зимовниках проживало, как правило, 3-4 семейных хозяйства. При каждом из них было по 5-6 казаков, каждый из которых, в свою очередь, имел нескольких (до 10) подвластных им молодчиков (начинающих казаков), были и наймиты (наемные солдаты). Главная задача зимовников — снабжать войско всем необходимым: продуктами питания, а если необходимо, и жильем при казацких походах. Наличие источников пресной воды или колодцев являлось, по-видимому, важнейшим условием при выборе места для зимовника: такое место находилось у обрывистого склона правого берега Кальмиуса.
Со временем казацкий зимовник Домаха превратился в городище, а потом и в крепость. Уже в 1611 году она стала центром обширной, но самой малонаселённой Кальмиусской паланки. Так в 1762 году, согласно «Истории Новой Сечи или последнего Коша Запорожского» А. А. Скальковского (1846 год), во всей паланке находилось 674 казака. В самой крепости находилась церковь, торговые лавки. Археологами в 1931 году во время строительства завода «Азовсталь» на левом берегу Кальмиуса были обнаружены землянки, в которых жили рыбаки-запорожцы, были найдены боевые топорики, керамические грузила для рыболовных сетей, часть якорной цепи, глиняные курительные трубки, фрагменты столовой посуды и другое. Кальмиус часто служил казакам обходным (обходя опасное усье Днепра) путём из Чёрного и Азовского морей к Запорожской Сечи (лодки-"чайки" тащили волоком или перевозили на волах на расстоянии 25 км от реки Кальмиус до реки Волчьей). Однако селиться казакам на побережье Азовского моря было категорически воспрещено Российской империей (трактат от 1700 года, Прутский мир 1711 года, Белградский мир 1739 года) — земли должны были быть «праздными».
Несмотря на это в 1734 год перестроенная и укрепленная «для защиты границ и покровительства рыболовству» крепость Кальмиус официально стала центром Кальмиусской паланки Запорожской Сечи. Кальмиусская паланка (казацкий военный округ) была крупнейшей в Области Войска Запорожского, охватывала кроме современной Донецкой также части Запорожской, Днепропетровской, Харьковской, Луганской и Ростовской областей и насчитывала более 300 зимовников.
30 апреля 1746 года царское правительство по указу императрицы Елизаветы Петровны разграничило конфликтующих запорожских и донских казаков по речке Кальмиус. Таким образом, вся территория нынешнего Донбасса разделилась на 3 части:
Область Войска Запорожского, разделенная на паланки:
Кальмиусская паланка (центр — Кальмиус, нынешний Мариуполь) — юг и центр Донецкой области к западу от Кальмиуса,
Барвенковская паланка (центр — Барвенково) — северо-запад Донецкой области;
Область Войска Донского — территория нынешней Луганской и Донецкой областей к востоку от Кальмиуса;
Изюмский Слободской Полк (центр — Изюм) — север Донецкой и северо-запад Луганской областей.
Материалы архива Коша Новой Сечи свидетельствуют, что в XVIII веке под прикрытием Домахи (более правильно Кальмиуса, Домахой, или Адомахой, называлось озеро, образованное в результате заболачивания западного ответвления Кальмиуса — засыпано в 1930-е годы) выросла Кальмиусская слобода, в которой благодаря стараниям полковника Андрея Трухи в 1754 году была построена каменная Святониколаевская церковь. То есть пользуясь тогдашними европейскими традициями, которые привязывали понятие города к каменным зданиям, в частности храмов, именно этот год можно считать основанием города. Так считает известный историк Восточной Украины В. А. Пирко.
В 1765 году после ликвидации слободских полков и образования Новороссийской губернии, территории не входившие в Войско Запорожское и Войско Донское вошли в состав Новороссийской и Слободско-Украинской губерний. В 1769 году крымские татары, совершая свой последний набег на украинские земли, ворвались и на территорию Кальмиусской паланки, разрушив сторожевое укрепление и убив весь отряд запорожских казаков (таким образом к времени основания города Павловска никаких постоянных населённых пунктов в устье Кальмиуса не сохранилось). После этого Российское правительство, не ожидая окончание войны с Турцией, в 1770 году приняло решение о перемещении части границы с Крымским ханством на 200 километров юго-западнее — с берегов реки Северский Донец на берега Берды и Конки, после чего Кальмиусская паланка оказалась внутри Российской империи. В ней начала возрождаться жизнь. Укрепление Кальмиус имело относительно небольшие размеры — квадрат 150 м на 150 м, стояло на высоком мысу правого берега Кальмиуса, было обнесено частоколом, а со стороны степи — земляным валом и небольшим рвом. В 12 верстах от устья выше по течению Кальмиуса (сейчас — пгт Сартана) находился форпост с двумя сотнями казаков во главе с полковником. Запорожцы также содержали 2 почтовые станции на этой дороге: на переправе через реку Кальчик (современный посёлок Аэродром у реки Кальчик) и над Белосарайским лиманом (окраина современной Ялты), на каждой из которых находилось по 8 ямщиков с лошадьми.
После заключения Кючук-Кайнарджийского мирного договора 1774 года территория Запорожья, в том числе и Кальмиусской паланки, была официально включена в состав Российской империи. С ликвидацией Области Войска Запорожского в 1775 году казаки были вынуждены покинуть устье Кальмиуса, а земли Кальмиусской паланки 14 февраля 1775 года вошли в состав Азовской губернии Екатеринославского наместничества (под названием «Кальмиусский уезд», кроме которого было ещё 8 уездов). Кальмиусский уезд при этом становился самым большим в губернии по площади. Центр Азовской губернии — губернский город Екатеринослав начал строиться в 1776 году у места впадения реки Самары в Днепр (администрация временно разместилась в Кременчуге). Вскоре названия некоторых уездов были изменены: Кальмиусский стал Павловским, Консководский — Александровским (сейчас — Запорожье), Волководский — Мариенпольским.