Фамилия Рустямов образована от личного имени Рустям — русской бытовой или диалектной формы тюркского имени Рустам. В основе лежит эпическое имя героя персидского эпоса «Шахнаме» — богатыря Рустама. В тюркских языках, особенно у татар, башкир, азербайджанцев, имя Рустам (или Рустям) было распространено как благопожелательное: родители надеялись, что сын вырастет сильным и мужественным, как легендарный витязь. Форма Рустям с «ё» (или «е» после твёрдого согласного) — характерная черта народного произношения, где безударное «а» переходило в более узкий звук. В русской среде такое имя могли записать как Рустям или Рустем, отсюда и разница в фамилиях Рустямов и Рустемов.

Суффикс -ов указывает на типичную русскую модель образования фамилий от отчества. Рустямов буквально означает «сын Рустяма». В отличие от фамилий на -ин, которые образуются от основ на -а/-я (например, Ильин), суффикс -ов присоединялся к основам на твёрдый согласный. Это говорит о том, что имя-основа воспринималось как мужское и склонялось по второму склонению (Рустям — Рустяма), что и дало форму Рустямов.

Географически фамилия Рустямов встречается в регионах с компактным проживанием татар и башкир — в Татарстане, Башкортостане, а также в Оренбургской, Челябинской областях. Встречается она и у азербайджанцев, но там чаще пишут Рустамов. Вариант Рустямов — более русифицированный, с адаптацией к русской фонетике и графике: буква «я» вместо «а» во втором слоге — это попытка передать редуцированный звук, который в тюркских языках ближе к мягкому «а» или «э».

В дореволюционной России носители фамилии относились в основном к крестьянскому или мещанскому сословию, реже — к духовенству (у татар-мусульман муллы и их дети тоже получали фамилии по отцу). Дворянских родов с такой фамилией не зафиксировано: она слишком поздняя и простонародная по происхождению. Ономастические справочники (например, работы А. Суперанской по тюркским фамилиям) подтверждают, что Рустямов — типичный пример перехода мусульманского имени в русскую фамильную модель в XIX–XX веках.