В другой стране козаков, на Дону, старые формы быта мирно уступали место новым отношениям к государству, непреоборимое могущество которого было сознано после неудачи Булавинского бунта. Еще в ноябре 1716 года атаман Максим Фролов писал князю Меншикову: «Пожалуй, государь мой и батко, светлейший князь Александр Данилович, подай руку помощии заступи великому государю о самых моих нынешних крайных нуждах, дабы мне быть в Войску Донском войсковым атаманом по вся годы без перемены за мою службу и за старость имянным его величества государя указом на писме, такожде как и бывший войсковой атаман Петр Емельянов был пожалован; а ныне я выбран войсковым атаманом с общего войскового согласия». В 1722 году атаман Василий Фролов, брат Максима, прислал в Москву сына и племянника «ради изучения в школе книг латинского и немецкого писания и других политических наук». Василий Фролов умер в следующем году; на его место выбрали Ивана Матвеева; но комиссия, назначенная для разбора турецких жалоб на козацкие разбои, приговорила его к уплате денег за разбитые им турецкие арбы. На Дон пришел императорский указ, что поэтому Матвеев не может быть атаманом, а назначается атаманом впредь до указу из старшин Андрей Иванов Лопатин. Козаки отвечали, что Лопатин «удовольствован, войсковым атаманством почтен».
На Востоке инородцы продолжали волноваться. Мы видели, что в 1720 году для успокоения башкирцев и вывода от них пленных отправлен был Сенатом полковник граф Головкин. Весною 1722 года он возвратился, привез чертеж Башкирской земли и объявил, что выслал беглых с 7 июня 1720 по 1 марта 722 года 4965 семей, а людей обоего пола — 19815. Но в 1724 году опять началось бегство к башкирцам, которые выходили против сыщиков боем. Отправлен был новокрещенин тайно, будто беглый, разведать, что делается у башкирцев. Башкирцы приняли его и сказали: «Для чего тебе жить в Казанском уезде: будет скоро война с Русью, и будет война не такая, что прежде была; снами будут сибирские и яицкие козаки». Приходили известия, что новокрещены чистят копья и стрелы точат, ясачные татары отказывались платить подушное и давать рекрут. У башкирцев было собрание в Уфимском уезде, на озере Берсевен; приехал батырь Алдарко с 700 человек, приехал сын изменника Сеитка, бежавший в 1707 году к киргизам, с ним приехало киргиз 500 человек; собирались башкирцы и татары отовсюду на это озеро, хотели осадить Уфу, потому что на Уфе трое судей, а они требовали, чтоб оставлен был один, а двоих отдать им, прибыльщики им не надобны.
Но при этих беспокойствах со стороны степной Азии внимание Петра не переставало обращаться на самую отдаленную азиатскую границу, к берегам Восточного океана: здесь нужно было удовлетворить требованию науки, выставленному Лейбницем, узнать, соединяется ли Азия с Америкою. 2 января 1719 года написана была инструкция геодезистам из навигаторов Ивану Евреинову и Федору Лужину: «Ехать вам до Тобольска и от Тобольска, взяв провожатых, ехать до Камчатки и далее, куды вам указано, и описать тамошние места, сошлася ль Америка с Азиею, что надлежит зело тщательно сделать». Евреинов и Лужин не узнали, сошлася ли Америка с Азией, они только доставили Петру карту Курильских островов в 1722 году. Петр, разумеется, не удовлетворился этим и в 1725 году написал инструкцию капитану Берингу: «1) Надлежит на Камчатке или в другом там месте сделать один или два бота с палубами. 2) На оных ботах (плыть) возле земли, которая идет на норд, и по чаянию (понеже оной конца не знают) кажется, что та земля — часть Америки. 3) И для того искать, где оная сошлася с Америкою (с Азиею), и чтоб доехать до какого города европейских владений и самим побывать на берегу, и взять подлинную ведомость, и, поставя на карту, приезжать сюды».