Семен Палей родился в Борзне, казаковал сначала в Нежинском полку, затем, овдовев, на Запорожье. Потом, когда Ян Собеский для борьбы с турками восстановил казачества на Правобережье, Палей поступил на королевскую службу, собрал горячие головы из Молдавии и Поднестровья и засел с ними в Фастове, получив от короля титул полковника. Здесь он активно занимался заселением безлюдных территорий и стал практически правителем Белоцерковщины. Формируется так называемая Палеивщина, территория от Полесья до Дикого Поля, управляемая по «казацким законам». Крестьяне здесь чуть ли не поголовно «показачивались», переставали платить налоги и работать на панщине. Нередко Палей со своими казаками занимал имения соседних польских панов. Многие из его людей просто разбойничали на дорогах, одним словом, вели образ жизни в стиле Запорожья. Палеивщина стала идеалом украинской вольницы, куда стекались крестьяне из всех районов Правобережья, а зачастую — и с левого берега, где жесткая политика Мазепы, направленная на установление государственных порядков, не нравилась многим.
Разумеется, очень скоро деятельность Палея стала вызывать сильное беспокойство и раздражение польских властей. Зная это, еще в 1688 году Палей впервые обратился к царям с просьбой разрешить переселиться в пределы Московского государства. Мазепа тогда, как мы говорили, отнесся к этому негативно, недолюбливая Палея, как всех «самовольцев», и не возражал, когда Голицын решил, что покровительство правобережным казакам поставит под угрозу мир с Речью Посполитой. Другое дело было теперь, в 1690 году. Встать на защиту своих братьев-казаков и к тому же досадить интриганам-полякам и тем самым повысить свой авторитет на Правобережье — все это было очень заманчиво.
У Палея к этому времени возникли большие неприятности с польскими властями. Дошло до того, что после неудачного нападения на Немиров его посадили в тюрьму. Пока он был в заключении, в Фастов явились униаты и попытались отобрать православную церковь, построенную им. Вернувшись, Палей не долго думая отрубил униатам головы, что, разумеется, не могло пройти безнаказанно. В конце мая 1690 года Палей писал Мазепе, что польское войско было направлено к Фастову, чтобы силой вынудить его к повиновению[337]. Осведомитель Мазепы запорожец Прокоп Лазука предупредил Палея, что некоторые его товарищи обещали выдать его полякам[338]. Трудно сказать, истинно ли было это предупреждение или это была уловка Мазепы. По крайней мере Палей во главе своего отряда присоединился к казакам гетмана и участвовал в успешном налете на Кизикирмен.
Награды участникам похода, разумеется, коснулись и Палея. Мазепа не поскупился в выражениях, подчеркивая его храбрость, и в Москве решили поддержать Палея. В начале 1691 года Мазепа по царскому указу посылает к нему своего человека с увещеванием оставаться в верности царю. Однако письменного подтверждения отправлено не было, гетман велел все сказать на словах, опасаясь повредить мирному договору с Речью Посполитой[339]. Палей продолжал засыпать Батурин просьбами о разрешении переселиться в Левобережную Украину. Ответ из Москвы был прежний: пусть вдет в Запорожье, а уж оттуда через некоторое время сможет перейти в Левобережье. Чтобы не отталкивать Палея, гетман обратился за поддержкой к своему доброму приятелю Льву Кирилловичу Нарышкину, и Палею тайно прислали бархат и соболей.
В марте 1692 года Палей вместе с левобережными казаками участвует в походе на Очаков. Казаки сожгли посады города и набрали богатую добычу[340]. Этот поход принес Палею небывалую славу. Казаки увидели в нем идеального вождя — храброго и счастливого. То, что казакам только небольшую часть добычи удалось вывезти из Очакова из-за страшного бездорожья и потери лошадей, в расчет не принималось. В Запорожье послышались возгласы: «Дадим Палею гетманство, вручим ему все клейноды. Палей пойдет уже не Петриковой дорогой, он знает, как украинских панов к рукам прибирать». В Крыму Палея, в свою очередь, сравнивали с легендарным Сирко, в свое время наводившим ужас на татар, пытались привлечь на свою сторону, пророчили судьбу Хмельницкого. Заискивания татар и восторженное отношение казаков начали понемногу кружить Семену голову. При личной встрече с Мазепой он так и заявил, что если царь не примет его немедленно на службу, то он найдет себе другое место. Гетман снова и снова писал в Москву, предупреждая, что если Палей перейдет к татарам, то запорожцы последуют за ним и это будет иметь крайне негативные последствия для России.