Андрей Легошин был одним из первых внештатных спасателей Комиссии по чрезвычайным ситуациям Совмина СССР. В составе спасательной службы Союза обществ Красного Креста и Красного Полумесяца с 1988 по 1992 г. участвовал в ликвидации последствий разрушительных землетрясений в Армении (Спитак и Кировакан), Исламской Республике Иран и Турции (г. Эрзинджан). Работать проходилось в условиях повторных подземных толчков и опасности обрушения аварийных зданий.

В июле 1992 г. Андрей Легошин перешел на работу в Государственный центральный аэромобильный спасательный отряд («Центроспас»), где прошел служебные ступеньки от спасателя до начальника отряда. Участвовал в миротворческой операции в зоне грузино-абхазского конфликта в г. Ткварчели, доставлял грузы гуманитарной помощи в блокадный город, участвовал в эвакуации 2089 человек на вертолетах через зону боевых действий.

За 10 лет специалистами отряда «Центроспас» было спасено более 2 тысяч человек.

Работая в Центральной Африке (Уганда, Танзания и Руанда), Легошин доставлял грузы гуманитарной помощи в лагеря беженцев и эвакуировал их. Под его руководством проводились спасательные работы по ликвидации последствий разрушительного землетрясения в городе Нефтегорске на севере Сахалина (май 1995 г.). Там при участии руководителя «Центроспаса» было спасено 79 человек.

Во время военных действий в Чечне в 1995 и 2000 г. Андрей Легошин работал в Грозном, проводил поиск и вывозил раненых и беженцев, престарелых и инвалидов, распределял продукты питания. В Югославии, в условиях межнационального конфликта, обеспечивал доставку грузов помощи в осажденные районы Боснии и Герцеговины.

В 2001 г. спасатель международного класса Легошин оказывал помощь пострадавшим при землетрясении в Индии, в 2002-м - участвовал в международной гуманитарной операции в Афганистане и ликвидации последствий катастрофического наводнения в Ставропольском крае. В 2003 г. эвакуировал российских граждан из Багдада, принимал участие в ликвидации последствий землетрясения в Алжире.

За время работы в МЧС Андрей Легошин награжден орденом Мужества, медалями «За отвагу», «За спасение погибавших». В декабре 2002 г. спасателю международного класса Андрею Легошину было присвоено почетное звание «Заслуженный спасатель Российской Федерации».

С января 2003 г. Андрей Легошин - заместитель начальника Департамента управления в кризисных ситуациях МЧС России.