Но собственно имя Наливайко стало известным со времени заключения запорожскими казаками договора с послом германского императора Рудольфа II, Ласотою, против турок. Заключив договор, казаки в течение 1594 и 1595 годов предприняли три похода против турок и их союзников, татар и молдавских господарей. Первый такой поход предпринят был Наливайко в конце июня месяца 1594 года с целью произвести диверсию в тылу турецкой армии. Наливайко составил около себя вольницу людей из разного народа, иногда беглецов и преступников, и с ними действовал против турок и татар. Не имея ни средств, ни союзников, а между тем видя наступавшую грозу со стороны турок, хотевших завоевать себе Венгрию, германский император Рудольф II еще в конце февраля месяца 1594 года просил, через собственного посла, правительство Речи Посполитой о том, чтобы оно не пропустило в Венгрию через свои владения турецких союзников татар. В то же время прислал своего посла к полякам и турецкий султан, прося пропустить татар в Венгрию через Украину. Поляки отказали туркам. Но, несмотря на этот отказ, татары все-таки собрались походом на Венгрию и решили идти через Украину. Узнав об этом, Северин Наливайко, состоявший тогда еще на службе у князя Константина Острожского, с позволения своего патрона, отправил письмо к коронному гетману Яну Замойскому и предложил ему свои услуги действовать против татар и не допустить их до соединения с турками. В своем письме Наливайко писал Замойскому, что он уже успел собрать вокруг себя охотников до войны, но без воли гетмана не желает выступать в поход, чтобы не дать повода считать своих ополченцев шайкой разбойников[168]. Что отвечал на это письмо Ян Замойский, неизвестно, но в конце июня Наливайко с казаками уже вышел против татар. Он старался о том, чтобы не допустить татар в Венгрию на соединение с турецким султаном Амуратом, однако не преуспел в этом, и татары, обманув казаков, проскакали в Венгрию через Покутье. Пробежав по следам татар до Теребовля и не видя возможности догнать их, Наливайко возвратился назад с большой добычей.
Возвратившись назад, Наливайко нашел нужным отправить, через двух своих посланцев, часть захваченной ими добычи в Запорожскую Сечь, желая загладить тем свою вину перед низовыми братчиками в том, что он во время походов Косинского сражался против запорожцев. Посланцы прибыли в Сечь 1 июля 1594 года, как раз в то время, когда там находился посол германского императора Рудольфа II, Эрих Ласота. Прибыв в Сечь, посланцы Наливайко прежде всего испросили прощение у запорожских казаков от имени Наливайко за то, что он некогда стоял против низовых казаков; но то произошло потому, что Наливайко служил киевскому воеводе, против которого враждовали запорожцы, и потому должен был повиноваться ему. Теперь Наливайко собрал возле себя от 2 до 21/2 тысячи человек казаков и с ними нанес поражение татарам, настигши их в Молдавии и отнявши у них от 3 до 4 тысяч лошадей. Узнав, что запорожское войско терпит большой недостаток в лошадях, Наливайко шлет своих посланцев в Сечь и через них извещает, что он готов разделить с низовыми молодцами свою добычу и подарить им 1500 или 1600 коней, лишь бы только запорожцы считали его своим другом. Если же честное низовое рыцарство подозревает его во враждебных к ним намерениях, то он готов явиться к нему лично в казацкое коло, сложить посреди него свою саблю и оправдаться от взводимых на него обвинений. А если честное рыцарство найдет его оправдания недостаточными, то он сам предложит отрубить ему голову собственной саблей. Однако ж он надеется, что низовые рыцари удовлетворятся его объяснениями, признают их основательными и навсегда будут считать его своим другом и братом, ибо что касается прошлого, то Наливайко состоял на службе у киевского воеводы еще раньше, чем запорожцы вступили в войну с Острожским; когда же возникшие между ними недоразумения окончились войной, то уже собственная честь не позволила ему, Наливайко, оставить воеводу, своего господина, которого хлеб он ел задолго перед тем и в службе которого состоял с давнего времени, почему и принужден был сражаться за него против его врагов[169].