Происходил из бедной дворянской семьи, родился в 1749 году в деревне Панихино Ново-Ладожского уезда Санкт-Петербургской губернии[1].
В 1760 году поступил в Морской кадетский корпус, в июле 1762 года был произведён в гардемарины и в этом же году совершил первое плавание от Кронштадта до Кольберга и обратно. В 1766 году он был произведён в мичманы и определён на службу в Балтийский флот, а в 1769 году был переведён в Таганрог.
В мае 1772 году получил чин лейтенанта и по время первой Турецкой войны был на разных судах ежегодно в крейсерстве на Чёрном море, причём в 1774 году командовал отдельной флотилией в Еникале. В 1775 году, по заключении Кючук-Кайнарджийского мира, Пустошкин, в качестве командира галиота «Буйвол» занимался описанием берегов Днепра и Южного Буга, затем был послан с поручением высшего начальства в Константинополь, а в следующем году был назначен командиром фрегата «Почтальон».
В мае 1777 г. произведённый в капитан-лейтенанты, Пустошкин в том же году сопровождал из Тамани в Еникале крымского хана Шагин-Гирея. В 1779 году командовал кораблём «Корон», а с 1780 по 1782 год находился в Балтийском флоте.
Получив 21 апреля 1783 года чин капитана 2-го ранга, Пустошкин в этом же году, в качестве флаг-капитана у вице-адмирала Ф. А. Клокачёва, на фрегате «Победа» был в плавании от Таганрога до Севастополя, после чего на боте «Битюг» делал промеры и опись берегов Днестровского лимана; затем командовал кораблем «Моджа». В 1784—1787 годах командовал Гниловской верфью в Таганроге. 1 января 1787 года Пустошкин был произведён в капитаны 1-го ранга, а вскоре за тем был назначен командиром Таганрогского порта.
В силу начавшейся новой войны с турками, на него была возложена обязанность построить в Таганроге два 40-пушечных фрегата и приготовить к походу 23 вооруженных судна. За успешное выполнение этого поручения он был награждён, 2 февраля 1789 года, орденом св. Владимира 4-й степени, а 14 апреля того же года, за отличие по службе, произведён в капитаны бригадирского ранга. В том же году, командуя отдельной эскадрой, Пустошкин крейсеровал около Крымского полуострова, а в следующем году — у устья Дуная. В следующем году он получил от князя Г. А. Потёмкина орден св. Владимира 3-й степени и 16 сентября был произведён в капитаны генерал-майорского ранга.