Фамилия Новомлинцева — редкий случай, когда географический корень почти не вызывает споров, а споры вызывает сам способ, которым фамилия появилась. В основе лежит топоним Новая Мельница или Новая Млинця. «Млин» по-украински и по-белорусски — мельница. Поэтому первое, что приходит в голову: предок жил при недавно построенной мельнице, на новом мельничном хуторе. Но если бы фамилию дали просто по месту жительства, мы бы, скорее всего, имели Новомельницев или Новомлинцев. Суффикс «-ев» здесь стандартный, а вот суффикс «-ин» в варианте Новомлинцева (женская форма) указывает на то, что исходная мужская фамилия звучала как Новомлинцев. Но откуда тогда «-ц-»?

Дело в том, что «Новомлинцев» — это не «сын человека с Новой Мельницы», а, вероятно, «сын Новомлинца». Форма на «-ец» в русских фамилиях часто означала прозвище по характерному признаку: «новомлинец» — это человек, который либо переселился с Новой Мельницы, либо работал на ней, либо владел ею. Суффикс «-ец» прибавляли к названиям мест, чтобы обозначить выходца оттуда (ср. «ростовец» — из Ростова). Потом это прозвище Новомлинец дало фамилию Новомлинцев — через притяжательный суффикс «-ев». То есть цепочка такая: Новая Мельница → Новомлинец (прозвище) → Новомлинцев (фамилия).

Географически фамилия тяготеет к южнорусским и украинским регионам, где слово «млин» было в ходу. Встречаются также варианты Новомлинский, Новомельницкий — они уже явно указывают на дворянское или духовное происхождение, поскольку суффикс «-ский» был престижнее. А вот Новомлинцев — фамилия крестьянская или мещанская, без претензий. Единственное, что может сбить с толку: прилагательное «новая» в названии мельницы. Это говорит о том, что поселение или сам объект были основаны позже соседних, старых мельниц. Так что предки Новомлинцевых, скорее всего, были из тех, кто осваивал новые земли или строил новое хозяйство на рубеже XVII–XVIII веков.