Федченко родился 7 февраля  1844 года в Иркутске (по другим сведениям в Барнауле). В гимназии он учился в Иркутске, где жил с родителями. Его отец владел золотоносным прииском, однако разорился и умер, когда Алексей Павлович заканчивал гимназию. В дальнейшем его и его мать материально поддерживал старший брат Григорий, к тому времени окончивший Московский университет и работавший преподавателем технического училища.

В 1860 году он с матерью переехал из Иркутска в Москву и поступил в Московский университет на естественное отделение физико-математического факультета. Будучи студентом он увлёкся ботаникой. В 1863 году он совершил своё первое путешествие — сопровождал своего старшего брата в научной экскурсии по солёным озёрам Южной России. В этой экспедиции он увлёкся энтомологией и составил очень хорошую коллекцию двукрылых и перепончатокрылых, что позволило ему затем на основе её описания опубликовать научную работу. Будучи студентом университета вместе с друзьями основал Общество любителей естествознания, антропологии и этнографии при Московском университете и был его учёным секретарём, что способствовало росту его авторитета и в серьёзных научных кругах.

После окончания университета в 1864 году со званием кандидата Федченко стал преподавать естествознание в Николаевском институте, а затем вскоре перешёл работать в университет, заняв пост инспектора студентов.

Основные научные труды А. П. Федченко были выполнены в области паразитологии и энтомологии. Им был открыт Заалайский хребет. Написана знаменитая книга «Путешествие в Туркестан»