Карьера Ушакова на ниве тайного сыска началась еще в петровское время. К анненскому времени он многое повидал и испытал. К 1731 году, когда его назначили начальником возрожденной Тайной канцелярии (петровская Тайная канцелярия под руководством П.А.Толстого при Петре II была ликвидирована), он сумел преодолеть обидный провал в своей карьере, который произошел с ним в мае 1727 года. Тогда его попутал бес – он был втянут в дело его начальника по Тайной канцелярии П.А.Толстого, да еще обвинили в недонесении, то есть по статье, за которую Ушаков за свою жизнь в сыске замучил множество людей. До этой неудачи карьера Ушакова шла вполне успешно.
Андрей Ушаков родился в 1670 году в бедной, незнатной дворянской семье. Согласно легенде, до тридцати лет жил в деревне с тремя своими братьями, деля доходы с единственного крестьянского двора, которым они сообща владели. Ушаков ходил в лаптях с девками по грибы и, «отличаясь большою телесною силою, перенашивал деревенских красавиц через грязь и лужи, за что и слыл детиною». В 1700 году он оказался в Новгороде на смотру недорослей и был записан в преображенцы. По другим данным, это явление Ильи Муромца политического сыска произошло в 1704 году, когда ему было уже 34 года.
Как бы то ни было, Ушаков довольно быстро сумел выслужиться. Поворотным моментом в его карьере стало расследование дел участников восстания Булавина в 1707–1708 годах. С тех пор Петр I начал заметно выделять среди прочих скромного и немолодого офицера. К середине 1710-х годов Ушаков уже входил в элиту гвардии, в своеобразную «гвардию гвардии». Он стал одним из десятка тех гвардейских майоров, особо надежных и многократно проверенных на разных «скользких» делах порученцев, которым царь часто давал самые ответственные задания, в том числе и по сыскным делам. Среди этих гвардейских майоров, людей честных, инициативных, бесконечно преданных своему Полковнику, Ушаков выделялся тем, что любил и умел вести сыскные дела. Он отличился в бестрепетном расследовании служебных злоупотреблений крупных чиновников, а в 1714 году Петр поручает Ушакову «проведать тайно» о кражах в подрядах, о воровстве в Военной канцелярии и в Ратуше, а также об утайке дворов от переписи. Для такого дела недостаточно рвения и честности, нужны были какие-то особые способности в сыскном деле. Ими, вероятно, Ушаков и обладал. По-видимому, по этой причине именно Ушакова царь поставил первым заместителем к П.А.Толстому в образованную в марте 1718 года Тайную канцелярию. По одной из версий, Ушаков был одним из убийц царевича Алексея в Трубецком бастионе Петропавловской крепости ночью 26 июня 1718 года. В отличие от других асессоров Тайной канцелярии, Г.Г.Скорнякова-Писарева и И.И.Бутурлина, Ушаков показал себя настоящим профессионалом сыска. Он много и с усердием работал в застенке. Интересная черточка характера Ушакова видна из дела баронессы Степаниды Соловьевой, которая в июне 1735 года была в гостях у Ушакова и за обедом жаловалась на своего зятя Василия Степанова. Она сказала, что зять «ее разорил и ограбил и при том объявила словесно, что в доме того зятя ее имеетца важное письмо». Хозяин сразу насторожился и спросил: «По двум ли первым пунктам?», то есть по наиболее серьезным политическим преступлениям. И хотя Соловьева уклонилась от ответа, в Тайной канцелярии вскоре завели на Соловьеву и ее зятя дело, а потом баронесса оказалась за решеткой и просидела в Тайной канцелярии несколько лет. Как видим, начальник Тайной канцелярии и за обеденным столом оставался шефом политического сыска. В награду за расследование дела царевича Алексея Ушаков в 1719 году получил чин бригадира и 200 дворов. С успехом он заменял и самого Толстого, который, завершив дело царевича, тяготился обязанностями начальника Тайной канцелярии. Многие сыскные дела он перепоручал Ушакову, который делал все тщательно и толково. К середине 1720-х годов Ушаков сумел укрепить свои служебные позиции и даже стал докладчиком у Екатерины I по делам сыска. Гроза, которая в начале мая 1727 года разразилась над головой Толстого, А.М.Девьера и других, лишь отчасти затронула Ушакова – он не угодил на Соловки или в Сибирь. Его лишь, как армейского генерал-лейтенанта, послали в Ревель. Во время бурных событий начала 1730 года, когда дворянство сочиняло проекты об ограничении монархии, Ушаков был в тени, но при этом он подписывал только те проекты переустройства, которые клонились к восстановлению самодержавия в прежнем виде. Позже, когда Анне Ивановне удалось восстановить самодержавную власть, лояльность Ушакова отметили – в 1731 году императрица поручила ему ведать политическим сыском.