Род. 5 (17) февраля 1884 года в поселке Железинский Павлодарского уезда Семипалатинской области, в семье казачьего офицера.

Учился в Сибирском пансионе казачьего войска и Сибирском кадетском корпусе (1886-1903 гг.), который неожиданно оставил воспитанником VII класса, получив свидетельство об окончании шести классов. В 1905 г. сдал экстерном экзамен за курс учительской семинарии.

С 1905 г. - преподаватель в начальных училищах Алтая (поселки Надеждинский и Большенарымский).

В 1907-1917 - учитель по вольному найму в приготовительном пансионе Сибирского казачьего войска, там же (до 1912 года) заведовал войсковой публичной библиотекой.

В мае 1911 года Новоселов сдал экзамен при Петропавловском реальном училище на звание учителя уездного училища, получив право преподавать географию.

С 1903 г. публикует в местной прессе (журнал "Степной край") свои первые рассказы. Совершил несколько научных экспедиций в Казахстан и на Алтай, в районы старообрядческих селений, изучал старинные архивы раскольников, записывал русский и казахский фольклор, выступал в печати со статьями и очерками этнографического характера ("Иртышский казак", "У старообрядцев Алтая", "Умирающая старина: к материалу по этнографии алтайских старообрядцев").

Действительный член Русского географического общества (РГО).

Автор циклов очерков "Алтайские этюды", "Степные картинки", "Дорожный кинемо" ( опубликованы в газетах "Алтайский вестник" и "Жизнь Алтая" в 1909-1915 годах); книги очерков "Лицо моей родины" (частично опубликованы в журнале "Сибирские огни" (1923, №№ 5-6; 1924, № 2, полностью в сборнике прозы А.Е.Новоселова "Беловодье", Иркутск, 1981).

В конце 1909 года Новоселов сблизился с группой писателей-областников - Е.И.Ершовым, А.С.Сорокиным, Н.В.Феоктистовым, Ф.А.Березовским, организовавших литературный кружок (просуществовал до 1916 года).

В этот период Новоселов активно выступал в сибирских и столичных изданиях: рассказы "Легкая жизнь" (Омский вестник. - 1910. - №№ 19-21), "Экзамен" (Омский вестник. - 1910. - №№ 94, 137), "Подсидел" (Дума. - 1910. - № 11), "Смерть Атбая" (Сибирские вопросы. - 1911. - №№ 42-44) и др. Это своеобразные этюды, "картинки", в которых угадывается что-то от художественной манеры и настроений чеховских рассказов. Многие "картинки" Новоселова представляют собой обработку записанных им казахских сказок - "Один и четверо" (Сибирские вопросы. - 1910. - № 7), "Лисица и волк" (Омский вестник. - 1910. - № 112) и др.

Известность Новоселову-прозаику принесли произведения об алтайских крестьянах-старообрядцах - рассказ "Жабья жизнь" (Летопись. - 1916. - № 11), повесть "Мирская" (Сибирский рассвет. - 1919. - №№ 11-12) и наиболее значительная среди них - повесть "Беловодье" (первоначальное название "Панкрат-беловодец". - Летопись. - 1917. - №№ 7-8, 9-10), повесть "Исишкина мечта" (Сборник "Жертвам войны". - Омск, 1915) - незатейливый рассказ о жизни честного и трудолюбивого батрака-казаха.
повестей:

На свои сбережения в 1917 году основал издательство "Мой край" и успел издать книгу стихов Г.А.Вяткина "Алтай" (Омск, 1917). Ввиду недостатка средств издательство через три месяца прекратило свое существование.

В апреле 1917 года I Сибирским казачьим съездом он был избран товарищем председателя Войсковой Управы Сибирского казачьего войска. В июне 1917 года вступил в партию эсеров.

Весной (по другим данным в сентябре) 1917 назначен Акмолинским областным комиссаром Временного правительства;
позднее Сибирская областная Дума избрала его в состав Временного Сибирского правительства, где он занимал пост министра внутренних дел. После роспуска Думы большевиками Новоселов уехал в Харбин; накануне колчаковского переворота вернулся в Омск, был арестован по распоряжению начальника Омского гарнизона.
Ему было предъявлено обвинение то в "бездействии власти", когда он был комиссаром Акмолинской области, то в прямом "соучастии в ноябрьском большевистском перевороте".

21 (по другим данным - 23) сентября 1918 года А.Е.Новоселов был убит без суда в тюрьме офицерамимонархистами.

Уникальный и обширный архив Новоселова жене удалось перевезти в Ленинград, где он погиб во время блокады в годы ВОВ.