Андрей Павлович Федоров родился 26 августа 1888 года в с.Мангуш Мариупольского уезда Екатеринославской губернии в крестьянской семье. Закончив двухклассное сельское училище, поступил в Мариупольскую гимназию. В 1905 году за участие в забастовочной движении учащихся был исключен из нее, позднее сдал экстерном экзамены и в 1909 году поступил в Новороссийский университет на медицинский факультет.
Участвовал в революционной деятельности партии эсеров, за что был исключен из университета и выслан из Одессы.
В 1910 году поступил на юридический факультет Харьковского университета. В 1912 году за участие в забастовке протеста против расстрела рабочих на Ленских золотых приисках был уволен из университета, арестован и выслан за пределы губернии. Проживал на Кавказе. В 1914 году экстерном закончил университет, получив профессию юриста.
В августе 1915 года А.П.Федоров был призван на военную службу и направлен на учебу в Александровское военное училище в Москве. В 1916 году его произвели в прапорщики и зачислили в 5 сибирский полк в Туркестане.
Находясь на службе в армии, А.П.Федоров вел революционную работу среди солдат, являлся членом полкового солдатского комитета. В 1917 году встал на сторону революции и принял в ней активное участие.
С приходом белогвардейцев в Туркестан А.П.Федоров был арестован, но в связи с тяжелой болезнью освобожден. Лечился в Ессентуках, где участвовал в работе подпольной коммунистической группы.
В конце августа 1919 года был арестован деникинской контрразведкой по обвинению в связях с большевиками. Белогвардейский суд приговорил его к расстрелу, однако в конце декабря того же года по "манифесту Деникина" был помилован и направлен в караульную роту во Владикавказ. В январе 1920 года бежал под видом кучера в Тифлис, где поступил на работу в качестве секретного сотрудника Особого отдела 10-ой армии.
С 1920 по 1922 год А.П.Федоров работал на Кавказе в качестве уполномоченного, а затем начальника отделения Особого отдела Батумского укрепрайона. В 1922 году откомандирован в Тифлис, а затем в Кутаис на должность начальника отделения Закавказской ЧК.
В 1922 году А.П.Федорова как чекиста, располагающего большим опытом работы, перевели в центральный аппарат ВЧК, где он работал вначале секретным сотрудником по загранице, а затем начальником Контрразведывательного отдела. В этой должности он оставался до 1933 года.
В 1922 году перед А.П.Федоровым как руководителем КРО ВЧК была поставлена задача по пресечению деятельности возглавляемого Б.Савинковым "Союза защиты Родины и свободы". В разработанной под руководством Ф.Э.Дзержинского операции "Синдикат-2" ему отводилась одна из главных ролей.
Выступая в качестве руководителя легендированной чекистами контрреволюционной организации "Либеральные демократы", А.П.Федоров неоднократно выезжал в Париж к Б.Савинкову , встречался с активистами его организации, а также с британским разведчиком С.Рейли . Бывая в Польше, он также встречался с сотрудниками разведки Генерального штаба этой страны, которых снабжал специально подготовленными дезинформационными материалами.
В этой операции А.П.Федоров проявил исключительную смелость, выдержку, находчивость и самообладание. Он выдержал неоднократные проверки, в том числе под дулом пистолета, которые устраивал ему ближайший помощник Савинкова — Павловский.
Благодаря профессиональному опыту А.П.Федорова, чекистам удалось склонить к приезду в СССР Б.Савинкова и его ближайших сотрудников.
За успешное выполнение сложного задания ОГПУ 5 сентября 1924 года А.П.Федоров был награжден орденом Красного Знамени. Коллегия ОГПУ присвоила ему звание "Почетный чекист".
С 1933 по 1937 год он работал начальником разведывательного отдела Управления НКВД Ленинграда и Ленинградской области.
В 1937 году по ложному обвинению в троцкистской деятельности он был арестован и приговорен к расстрелу.
В 1956 году А.П.Федоров реабилитирован посмертно.