Царский советник побежал к царю и рассказал, какую службу задать стрелку, чтобы он назад не вернулся. Царь посылает за Андреем.
— Ну, Андрей, сослужил ты мне службу, сослужи другую: ступай в тридесятое царство и добудь мне кота Баюна. Не то мой меч — твоя голова с плеч.
Пошёл Андрей домой, ниже плеч голову повесил и рассказывает жене, какую царь задал ему службу.
— Есть о чём кручиниться! — Марья-царевна говорит. — Это не служба, а службишка, служба будет впереди. Ложись спать, утро вечера мудренее.Андрей лёг спать, а Марья-царевна пошла на кузницу и велела кузнецам сковать три колпака железных, железные клещи и три прута: один железный, другой медный, третий оловянный. Утром рано Марья-царевна разбудила Андрея:
— Вот тебе три колпака да клещи и три прута, ступай за тридевять земель, в тридесятое царство. Трёх вёрст не дойдёшь, станет одолевать тебя сильный сон — кот Баюн на тебя дремоту напустит. Ты не спи, руку за руку закидывай, ногу за ногу волочи, а где и катком катись. А если уснёшь, кот Баюн убьёт тебя.
И тут Марья-царевна научила его, как и что делать, и отпустила в дорогу. Скоро сказка сказывается, не скоро дело делается — пришёл Андрей-стрелок в тридесятое царство. За три версты стал его одолевать сон. Надевает Андрей на голову три колпака железных, руку за руку закидывает, ногу за ногу волочит — идёт, а где и катком катится. Кое-как выдержал дремоту и очутился у высокого столба.
Кот Баюн увидел Андрея, заворчал, зауркал да со столба прыг ему на голову — один колпак разбил и другой разбил, взялся было за третий. Тут Андрей-стрелок ухватил кота клещами, сволок наземь и давай оглаживать прутьями. Наперво сёк железным прутом; изломал железный, принялся угощать медным — и этот изломал и принялся бить оловянным. Оловянный прут гнётся, не ломится, вокруг хребта обвивается. Андрей бьёт, а кот Баюн начал сказки рассказывать: про попов, про дьяков, про поповых дочерей.
Андрей его не слушает, знай охаживает прутом. Невмоготу стало коту, видит, что заговорить нельзя, он и взмолился:
— Покинь меня, добрый человек! Что надо, всё тебе сделаю.
— А пойдёшь со мной?