Quelimane significa em Swahili Monte, pois os nativos diziam-se originários do monte limane, aquando da chegada dos Portugueses. Assim, é possível que os intérpretes africanos que acompanhavam o Vasco da Gama, conhecendo o significado do prefixo Qui em lingua bantu, ao ouvirem os chuabos a designarem-se limane, passaram a chama-los Quilimane, que significa aqueles que dizem/ falam limane.

Uma outra versão refere que quando os portugueses desembarcaram pela primeira vez no porto que mais tarde se denominou Quelimane, o chefe da povoação, de descendência muçulmana, serviu de interprete entre os portugueses e os naturais. Em Swahili haliman significa interprete.

Também há quem derive o termo de culima que significa cultivar em várias linguas bantu. Porém Cabral acredita que tal analogia não passa de pura fantasia. Entre os naturais a povoação era conhecida por Chuabo que em língua local significa missanga grossa.

Em 1994 a cidade de Quelimane foi elevada a categoria de distrito Municipal, de harmonia com a Lei nO 3/ 94 de 13 de Setembro, revogada pela Lei n.o 2/97 pela qual foi elevada a categoria de Município.