Казаки не могли противостоять многотысячным татарским ордам и, натерпевшись от них всяких бед, обратились к русскому царю Михаилу Федоровичу с просьбой, «дабы он, великий государь, их, казаков, милостиво принял под царскую свою державу, обещаясь служить ему, великому государю, и наследникам его». Казаки отправили в Москву послов, «объявив через них о всех своих обстоятельствах, просили у его царского величества милостивой защиты». Царь Михаил Федорович «пожаловал им грамоту на реку Яик с находящимися при ней реками и протоками и со всякими угодьями, от вершин той реки до устья, и чтобы им на той реке жить и владеть, и великому государю служить казачью службу и набираться на житье вольными людьми».
Эту драгоценную грамоту казаки не сберегли, она сгорела при пожаре, поэтому от каждого русского царя, вступавшего на престол, они обычно просили новую грамоту, подтверждающую их права.
Рождение же Яицкого городка — столицы казачьего войска — Рычков по времени относит примерно к концу XVI века На основе известий яицких старшин он повествует, что одна из основных казачьих общин произошла от бывших на Каспийском море удалых людей, предводительствовал которыми донской казак Нечай. Набрав восемьсот человек себе подобных, он с этой грозной ватагой спустился на судах вниз по Волге к морю, где долгое время промышлял грабежом караванов персидских и армянских купцов. Но однажды буря разбила многие суда казаков, а оставшиеся занесла в устье Яика. Нечай поднялся вверх по незнакомой реке и при впадении в нее степной речки Рубежная облюбовал удобное место, где в 1584 году застроил селение, что в сорока верстах выше будущего Яицкого городка.
Поотдохнув и собравшись с силами, Нечай вскоре повел свою дружину в далекую Хиву в надежде захватить там легкую добычу. Ему поначалу повезло: хивинский хан со всем своим войском находился в отлучке, ведя войну с бухарцами. Нечай быстро завладел городом Хива и его богатствами, взял себе в жены ханскую жену. Как пишет Рычков, «Нечай и бывшие с ним казаки несколько времени жили в Хиве во всяких забавах и об опасности весьма мало думали; но та ханская жена, сильно полюбив его, Нечая, советовала ему: если он хочет живот свой спасти, то должен он со всеми своими людьми заблаговременно из города убираться, дабы хан с войском своим тут его не застал; и хотя он, Нечай, той ханской жены наконец и послушал, однако не весьма скоро из Хивы выступил, и в пути, будучи отягощен многочисленной и богатой добычей, скоро следовать не мог; а хан, вскоре потом возвратись из своего похода и видя, что город его Хива разграблен, нимало не мешкая со всем своим войском в погоню за ним, Нечаем, отправился, и через три дня настиг его на реке, именуемой Сырдарья, где казаки через горловину ее переправились, и напал на них с таким устремлением, что Нечай с казаками своими, хотя и храбро оборонялся и многих хивинцев побил, но напоследок со всеми имевшимися при нем людьми побит, кроме трех или четырех человек, которые, уйдя от того побоища, в войско яицкое возвратились и о его погибели рассказали… Несколько лет после того яицкие казаки селением своим перешли к устью реки Чаган, на то третье место, где ныне яицкий казачий город находится».
Войско представляло собой несколько общин древневечевого устройства, где все, как в старину на вече, имели право голоса, хотя и было выборное начальство — атаман, которому дозволялось вести повседневные дела, суд и расправу над повинными казаками. Атаман и его помощники — старшины избирались из авторитетных казаков. Все важные дела решались сообща в Войсковом кругу. Определенного срока службы у казаков не было, недаром они называли себя вольными людьми.
Но такая их самостоятельность вредила общим задачам государства. Вот почему русское правительство с начала XVIII века стало ограничивать права и волю казаков, требовать повиновения самодержавной власти. Петр I, не желая видеть какую-либо часть государства независимой, удалившейся от центрального руководства, издал указ, по которому Яицкое войско с 10 марта 1721 года было передано в ведомство Военной коллегии с одновременным подчинением астраханскому губернатору. При образовании в 1744 году Оренбургской губернии яицкие казаки по всем внутренним делам и распорядкам стали подчиняться непосредственно Неплюеву.
