Фамилия Деулина образована от личного прозвища или имени Деуля (Деула). Самая прямая версия связывает его с ярославским глаголом «деулить» — «есть со вкусом». Скорее всего, прозвище получил человек, который любил и умел хорошо поесть. Чуть реже встречается предположение, что так могли назвать искусного повара, кормильца, то есть прозвище указывало на профессию предка.

Есть и другая, менее очевидная версия. В некоторых говорах деулой называли глупого человека. В этом случае имя могло быть охранительным: родители нарекали сына Деулей, надеясь, что он вырастет умным и прозорливым, — так называемое имя-оберег.

Отдельного внимания заслуживает тюркская гипотеза. Фамилия могла возникнуть в мусульманской среде от имени Деули (Даули). Оно образовано от тюркского корня «дау» («большой, старший, первый, главный») и арабского «гали» («великий, возвышенный, дорогой, могучий»). Имя Гали широко известно в исламском мире: его дают в честь зятя пророка Мухаммеда. Таким образом, имя Деули могло означать «старший сын по имени Гали».

Первые документальные упоминания относятся к XVII веку. В «Ономастиконе» академика Веселовского записан посадский человек Аким Деулин, который в 1656 году жил в Казани. Сведения о носителях фамилии встречаются и в более поздних архивных документах. В Книге памяти Республики Башкортостан отмечены жители села Петровка Зилаирского района: Деулин Осип Иванович (1882 года рождения) и Деулин Иван Родионович (1883 года рождения). В документах Мурманской области значится Деулин Моисей Афанасьевич (1876 года рождения), который проживал в Челябинской области, в деревне Кужакуль Ялано-Катайского района.