La raíz andalusí madína (ár. clás. madīna) tiene el significado principal de 'ciudad'. Cuando va seguida de un segundo término —en la construcción posesiva conocida como estado constructo— la voz madína adquiere una t final (la tā' marbūṭa) antes de agregarse ese segundo elemento; p. ej. Madínat Sálim (ár. clás. Madīnat Sālim) 'la ciudad de Sālim' > Medinaceli. Cuando a esta t le sigue una consonante, la t suele desaparecer en la forma romance posterior (así Medinaceli); en cambio, si le sigue una vocal, la t se conserva; p. ej. Madínat Iyih 'la ciudad de Iyih' > s. XIII "Medina Tea" > Minateda (Hellín, Albacete) (Pocklington_Iyih 188).

Además de 'ciudad', madína también significa 'ciudad capital de una región'; p. ej. madínat Tudmír (ár. clás. madīnat Tudmīr) 'la capital de la cora de Tudmir'. Este doble sentido crea una situación ambigua, con efectos importantes para la toponimia, porque madínat Tudmír significa tanto 'la ciudad capital de Tudmir' como 'la ciudad de Tudmir'. Por este motivo el lugar llamado Murcia, que pasó a ser la capital de Tudmir en 825, empezó a denominarse madínat Tudmír, y el topónimo Murcia desapareció completamente de las fuentes escritas durante más de dos siglos. Lo mismo le pasó a Granada, la romana Iliberri, que dio su nombre a la cora islámica de Ilbíra (ár. clás. Ilbīra). Cuando los musulmanes trasladaron la capitalidad de la cora de Ilbīra desde Granada hasta los alrededores de Atarfe, empezaron a llamar la nueva capital madínat Ilbíra, trasladando el nombre Ilbīra de Granada a Atarfe. Más tarde la capitalidad regresó a Granada, pero la sierra situada detrás de Atarfe, a 12 km al O de Granada, sigue llamándose hoy, por este motivo, la Sierra de Elvira.

Un tercer significado de madína que se documenta en al-Andalus es 'madriguera, ratonera' (DozySuppl II 583). Según al-Idrīsī (s. XII), el paisaje de las Islas Fluviales del Río Guadalquivir se llamaba al-Madāyin 'las madrigueras o ratoneras', empleando uno de los plurales de madína (IdrisiDescr 215).

En la lengua clásica los plurales de madīna son mudun y madā'in, los cuales se registran en el árabe andalusí como mudun (pronunciación /múdun/ o /mudún/) y madáyin (pronunciación /madéyin/).

El diminutivo podía tener dos vocalizaciones en el árabe andalusí: mudáyna y mudáyyina (DictAndArabic 495; LexTopAnd 266); de allí proceden los diferentes topónimos Almudena, Almudaina, Almudema.

Apenas se documentan voces romances derivados de madína. Solo en castellano parece haber rastros claros de la existencia de un antiguo vocablo almedina o medina. El Diccionario histórico de la lengua española recoge almedina, en documentos de los siglos XII-XIII, con el significado 'núcleo central, generalmente murado, de una ciudad' (DHLE II 486). En cambio, la forma madina era la corriente en los siglos XV y XVI. Notablemente, Nebrija (c. 1495) indica el significado 'villa en muchas partes' y P. de Alcalá (1505) 'villa' (NTLE VII 6599).