Родился в городе Исилькуле в семье железодорожника. В мае 1942 года в неполные 18 лет его призвали в ряды Рабоче- Крестьянской Красной армии. Направили на Дальний Восток г. Сучан там и проходил курс молодого бойца. Война застала его во время службы в 117 полку 32 дивизии МВД, который охранял стратегические важные объекты на Дальнем Востоке. Его в числе 145 лучших стрелков направили в учебное подразделение снайперов. После успешной сдачи экзаменов Андрея Емельяновича направили в подразделение на участок Курской дуги. Выполнял важные задачи по подавлению огневых точек и уничтожению офицеров противника. В 1943 году в ходе боя был контужен и тяжело ранен. Поправив здоровье, весной 1944 года его направили для прохождения службы в 59(Гродековский) пограничный отряд. Служил он на пограничной заставе "Краево",где в должности старшины заставы и инструктора службы собак проходил службу легендарный Никита Фёдорович Карацупа со своим четвероногим другом Индусом. После войны Новосельцев Андрей Емельянович, продолжил военную службу по охране государственной границы Советского Союза. Получил много наград,среди них ордена Отечественной войны 1 и 2 степеней, медали "За отвагу ","За боевые заслуги ","За победу над Германией ","За победу над Японией ".