В 1910 году Федоров поступил на юридический факультет Харьковского университета. В 1912 году за участие в забастовке протеста против расстрела рабочих на Ленских золотых приисках он был исключен из университета и выслан за пределы Харьковской губернии. Жил на Кавказе. В 1914 году экстерном окончил университет, получив диплом юриста.

В августе 1915 года Федоров был призван на военную службу. Окончил Александровское военное училище в Москве и был направлен прапорщиком в 5-й Сибирский полк, расквартированный в Туркестане. На службе в армии Федоров вел революционную работу среди солдат, избирался членом полкового солдатского комитета. В 1917 году принимал активное участие в революционных событиях в России, поддержав Октябрьскую революцию.

С приходом белогвардейцев в Туркестан Федоров был арестован и выслан на Кавказ. Принимал участие в работе подпольной коммунистической группы. В конце августа 1919 года деникинская контрразведка напала на след подпольщиков, и Федоров был вновь арестован. Белогвардейский суд приговорил его к расстрелу, однако в конце декабря того же года по «манифесту Деникина» он был помилован и направлен на «перевоспитание» в караульную роту во Владикавказ. В январе 1920 года бежал в Тифлис, где поступил на работу секретным сотрудником Особого отдела 10-й армии.

С 1920 по 1922 год Федоров работал на Кавказе в качестве начальника отделения Особого отдела Батумского укрепрайона. В 1922 году был откомандирован в Кутаиси на должность начальника отделения Закавказской ЧК.

В 1922 году Федоров был переведен на работу в центральный аппарат ГПУ. Являлся активным участником операции «Синдикат-2», завершившейся в 1924 году выводом в СССР и арестом руководителя террористической белогвардейской организации «Народный союз защиты Родины и свободы» Бориса Савинкова. В данной чекистской операции Федорову отводилась одна из главных ролей.

Через эмиссара Савинкова в Москве Федоров вышел на самого руководителя белогвардейской организации. Выступая в качестве лидера легендированной чекистами организации «Либеральные демократы», разведчик неоднократно по заданию ГПУ выезжал в Париж и другие европейские страны, где встречался с Савинковым и активистами его организации, а также с британским разведчиком Сиднеем Рейли. Бывая по заданию Дзержинского в Польше, Федоров встречался с сотрудниками военной разведки этой страны, которых снабжал специально подготовленными в Москве дезинформационными материалами.

Борис Савинков настолько поверил в реальность существования «Либеральных демократов» и словам Федорова о том, что этой организации нужен энергичный вождь, что в августе 1924 года решился лично посетить СССР. Савинков был арестован чекистами на конспиративной квартире в Минске и доставлен в Москву на Лубянку. Арест вызвал у террориста, заявлявшего, что он не боится смерти, серьезный надлом и полную капитуляцию. Допросы Савинкова вели Артузов и его заместитель Пиляр. Он признал свое поражение и дал высокую оценку работе чекистов.

Что же касается самого Федорова, то в операции «Синдикат-2» он проявил исключительную смелость, находчивость и самообладание. Он выдержал неоднократные проверки со стороны польской контрразведки, а также со стороны ближайшего помощника Савинкова полковника Павловского, который требовал от разведчика признания в своей принадлежности к ВЧК.

В 1924 году Андрей Павлович был награжден орденом Красного Знамени, а позже – нагрудным знаком «Почетный работник ВЧК – ОГПУ».

Приведем выдержку из рапорта заместителя начальника контрразведывательного отдела ГПУ – ОГПУ Романа Пилляра на Федорова, представленного к государственной награде за участие в операции «Синдикат-2»: