Il disegno dello stemma cittadino ha alimentato la leggenda (attribuita a Luigi Tarelli, monaco di Casarano), che la città abbia avuto origine da tre masserie, denominate San Basilio, Sant'Egidio e San Vito che, unite insieme come le maglie di una catena, avrebbero formato il primo nucleo abitato. Emilio Panarese, storico e studioso del posto, richiama invece ed integra precedenti interpretazioni di storici locali dell'ottocento. A suo avviso il nome deriverebbe dal toponimo di origine messapica e quindi illirica "mal", notevolmente diffuso in tutta l'area mediterranea (e non solo nel Salento). Il significato del toponimo, in contrasto con la pianura su cui è adagiata la città, ma concorde con la fantasia degli abitanti (che vedevano un monte per ogni piccola sopraelevazione), sarebbe quindi quello di altura, cima o monte. La forma latinizzata "Malliae" corrisponderebbe a Mallia, toponimo dell'isola di Siro, nelle Cicladi, e a Malia, antica città dell'isola di Creta.