Sułtan Muhammad Quli Qutub Shah, piąty władca z dynastii Qutb Shahi wybudował Charminar w 1591, zaraz po przeniesieniu stolicy z miasta Golkonda do Hajdarabadu[1]. Budowla ta powstała jako dziękczynienie za zwycięstwo w walce z epidemią dżumy w mieście. Podobno sułtan modlił się o zakończenie epidemii, która niszczyła jego miasto i przysiągł wybudować meczet dokładnie w tym miejscu, jeżeli jego modlitwa zostanie wysłuchana. Nazwa Charminar wywodzi się prawdopodobnie od czterech wież – minaretów – tego meczetu, a dokładniej od słowa char znaczącego w języku urdu oraz w perskim "cztery", a także od arabskiego słowa minar lub manar znaczącego dosłownie "wieża".

Meczet wzniesiono przy użyciu granitu i kamienia wapiennego połączonego zaprawą wapienną, a także marmuru. Początkowo meczet był ulokowany dokładnie w samym centrum miasta i tak dokładnie zaplanowany, że z każdej z czterech stron meczetu można było dostrzec granice ówczesnego Hajdarabadu. Dzięki temu miejsce, w którym przecinały się obie drogi, a które wypadało dokładnie pod meczetem, było jednym z najbardziej ruchliwych w tamtych czasach. Istnieje także legenda, według której istnieje podziemny korytarz łączący pałac w Golkondzie z Charminarem, które miało potencjalnie służyć jako droga ucieczki w razie niebezpieczeństwa grożącego władcom z dynastii Qutub Shahi podczas oblężenia miasta. Niestety lokalizacja tunelu nie jest znana.