Після відносно спокійного козакування на Чернігівщині (Семен, як і його батько, був записаний до реєстру Ніжинського полку) Палій подається на Січ. Тут завдяки своїй природній мудрості, розважливому характеру та військовим здібностям він висувається в перші ряди кошової старшини. Восени 1683 р. С.Палій вже очолює один із загонів запорожців, що допомагав королю Яну III Собеському розгромити турецькі війська у післявіденському поході польської армії до Угорщини. Про значущість цієї допомоги говорив в одному із своїх листів Ян III, називаючи С.Палія "віденським богатирем".
Повертаючись із походу, Палій вирішив не йти з козаками до Січі, а залишитися в Правобережній Україні, яка після довголітніх воєн перетворилася в "пустинне поле". Влітку 1684 р. С.Палій зупинився біля І Немирова, де була резиденція правобережного українського гетьмана І А.Могили. Однак Палій не бажає виконувати накази Могили, більше того, він навіть намагається усунути його з посади. Це йому не вдається, і він повертається на Запорожжя. Але через деякий час, восени того ж року, вже з більшою кількістю козаків Палій знову з'являється на Правобережжі. Відтоді розпочинається активна діяльність полковника, яка мала не лише воєнний, а й державотворчий та колонізаційний характер.
Заходи Палія, що мали на меті відродження зруйнованого краю і захист його від турецько-татарських нападів, підтримувалися королівським урядом, який видав йому, а також полковникам Самійлу Івановичу (Самусю), Андрію Абазину та Захарію Іскрі привілеї, що узаконювали певні військово-адміністративні права козацької старшини на території Київщини та Брацлавщини. Стародавні "права та вольності Війська Запорозького" підтверджувалися також постановою вального сейму s від 16 лютого 1685 p. Вже 25 серпня того ж року С.Палій, перебуваючи в Білій Церкві, видав універсал, в якому сповіщав усіх, хто проїжджав територією Білоцерківського полку (особливо купців), про введення ним мита на користь козацької адміністрації.
Невдовзі на Правобережжя потягнулися люди з Лівобережної України, молдавських та білоруських земель. Якщо в 1690 р. у Фастові, який був обраний Палієм для своєї резиденції, було лише кілька сотень дворів, то через три роки їх нараховувалося вже близько трьох тисяч. Протягом наступних років тривав поступовий процес відродження правобережних містечок і сіл, які швидко заселялися завдяки захистові правобережних козаків під керівництвом С.Палія. Місцева польська шляхта, яка також поверталася до "дідичних" маєтків, скаржилася на те, що козаки, починаючи з 1687 p., будують свою "удільну" державу і не зважають на польські закони.
У 1688 p. С.Палій вперше звертається до московського уряду з проханням об'єднати Правобережну і Лівобережну Україну в єдиній Гетьманській державі під зверхністю царя. Однак через укладений між Польщею і Москвою в 1686 p. "Вічний мир" його ініціатива не була підтримана. 21 квітня 1690 p. С.Палій звернувся до Івана Мазепи з листом, в якому повідомляв лівобережного гетьмана про вдалу битву з татарами під Білою Церквою, а також просив його посприяти в тому, щоб "через милість вашу у пресвітлих монархів, аби прийнятий був". Отримавши відмову царського уряду, який не бажав порушувати московсько-польську угоду, правобережний полковник вирішив запевнити короля Яна III в своєму підданстві. У листі до польського монарха від і 30 травня з Фастова Палій писав: "... впавши до ніг В.К.М. пана нашого милостивого, чинимо подяку і вірну зичливість до останку хиття мого, як вірний підданий В.К.М., з людьми полку мого служити неодмінно готовий..." Крім того, козацький полковник просив короля захистити його від "гніву" великого коронного гетьмана С.Яблоновського, і який разом із полком П.Апостола-Щуровського не давав Палієвим козакам розміщуватися на "консистенціях", які раніше були визначені йому королівським урядом. Також С.Палій скаржився на білоцерківського коменданта С.Раппе, який, випустивши його з в'язниці за королівським наказом, не віддав йому "пернач від В.К.М. мило даний, при тім ще риштунок оправний і коні і інші речі". Наприкінці листа полковник прохав Яна III надіслати додаткову плату для його війська, бо присланих 2 тис. злотих, які прийшли перед тим із Варшави, не вистачало для утримання полку,
Утвердження козацького устрою на Київщині викликало "справедливе" обурення місцевої шляхти та духовних осіб, адже на їхні землі стала поступово поширюватися влада С.Палія. Щоб убезпечити себе від можливого конфлікту з королем, козацький полковник запевнював польського правителя, що не має наміру займати "ті добра, які Богу і Церкві належать". Повідомлений про це з Варшави, київський бискуп А.Залуський дозволив козакам Палія розташовуватись у його володіннях за умови, щоб йому не робили "ущербу в арендах". Завдяки таким заходам правобережного полковника взаємини між ним і королівською владою, незважаючи на періодичні сутички з місцевою польською шляхтою, були досить стабільними.
Восени 1691 р., після вдалого походу на Білгород, С.Палій, повернувшись до своїх володінь, наказує стратити нобілітованого шляхтича, козацького полковника П.Апостола-Щуровського. "Такого великого утиснення Війська нашого від Апостола не могли витримати", - виправдовувався він перед королівським комісаром С.Дружкевичем. Водночас Палій запевнював польського урядовця, що не має наміру "шукати собі з Військом іншого пана", хоча перед там неодноразово звертався до І.Мазепи з проханням прийняти його під гетьманську булаву і зверхність царя.
С.Дружкевич, на відміну від короля, не довіряв запевнянням полковника, про що свідчать його листи до Варшави. Саме тому в червні 1692 р. до Фастова прибула делегація київського стольника Кшиштофа Ласки, якого Палій також переконав у своїй прихильності до монарха Речі Посполитої. Після 1692 р. польські військові частини в Правобережній Україні діяли вже не так енергійно. Хоча вони й витіснили Палієвих козаків із Полісся, планований наступ на Фастів не відбувся.
Після допомоги військам І.Мазепи у відбитті нападу "ханського" гетьмана Петра Іваненка (лютий 1693 р.), а також спільного з лівобережними полками походу на Кизикермен С.Палій намагався відновити свої позиції, що похитнулися після захоплення відділами регіментаря Бальцера Вільги значної території Фастівського полку. Для цього він знову вдається до дипломатичних заходів. У листі до Яна III Собеського від 16 травня С. Палій виправдовував те, що без дозволу короля ходив у похід з лівобережними полками, існуванням "спільної і нерозривної монаршої ліги" проти турків. Він сповіщав про вдалі дії правобережних козаків, прохав прийняти свого сотника Павла з татарським "язиком" і обіцяв для підтвердження своєї вірності королеві відновити боротьбу з турецько-татарськими військами на подільських землях. "... Щоб не був випущений з ласки і опіки монаршої з полком моїм найпокірніше прошу", - писав Палій наприкінці листа.
На початку 1694 р. поновлюється наступ польських військ під командуванням С.Яблоновського на Фастів. С.Палій вислав до короля своїх представників, прохаючи пояснити, на якій підставі коронний гетьман здійснив на нього напад, адже він неодноразово складав присягу польському монарху. Можливо, саме після цього звернення Ян ІІІ наказав припинити воєнні дії проти правобережних козаків, бо відділи регіментаря Б.Вільги відступили з території Фастівщини на Полісся. Крім того. Палій уклав перемир'я з Вільгою і Яблоновським - "... вимушений з ляхами з'їзджатися і учинити мир для того, щоб війська більше польські на мене не наступали". Внаслідок примирення козацькі війська звільнили більшу частину Фастівського полку, де знову розмістилися сотні С.Палія. Восени того ж року відділи правобережного полковника здійснили успішний похід на буджацьких татар. Повертаючись до своєї резиденції, Палій надіслав білоцерківському комендантові "реляцію" з повідомленням про знищення семи татарських поселень. Крім того, він відправив до короля і коронного гетьмана кількох узятих у полон "язиків", яких супроводжували його козаки. Саме про них писав до короля, перебуваючи в Батурині, польський посол К.Ісарович: "Пане милостивий, відаю, що у В.К.М. були двоє козаків у Жовкві від Палія, коли В.К.М. полював у полі і вони теж були в полі і кланялись В.К.М.; скоро їх гетьман коронний і каштелян краківський відправив до Палія. А як тільки прийшли, то і тієї ж години послав їх до Мазепи в Батурин, яким певно, гроші дано. щоб віддали Палію".
