As per an inscription over the central doorway, Khawja Shahbaz Mosque was built in 1679 AD by Khwaja Shahbaz, a prominent merchant of Dhaka during the viceroyalty of prince Muhammad Azam. Presently it is located near Curzon hall and Teen Netar Mazar (tomb of three national leaders).

Khawja Shahbaz Mosque is positioned near Mir Jumla’s Gate (Dhaka Gate), one of the oldest Mughal architectures of Dhaka, signifying the prominence of the place. The mosque was probably constructed after the death and subsequent construction of the Khawja Shahbaz Tomb. However, the mosque may have existed before as an insignificant structure. The tomb is located at the east of the mosque courtyard and is an integral part of the mosque complex, follows the same architectural style. The Khawja Shahbaz Mosque is a typical Bengali Mughal type (Asher, 1984); that is, a rectangular structure crowned with three-domes.

The mosque has an oblong plan of 69'3" x 29'3" externally and 56'8" x 16'0" internally. The structure is divided into three equal interior bays, roofed over by three fluted, bulbous domes, resting on drums. Of the three equal sized domes, the central one rests over a slightly elevated bay. The eastern façade has three arched openings while the northern and southern façades have a single arched opening to the prayer hall. Two wide multi-cusped transverse arches, issuing from twin engaged brick pillars, divide the interior of the mosque into three equal bays, each roofed over with a low shouldered dome on a cylindrical drum. There are three mihrabs, each aligned with the three entrances at east and the central portion of the qibla wall is projected westward from the ground to the roof. Stylistically this kind is known as Shaista Khani architecture, commonly found in and around Dhaka.

The rectangular structure is buttressed by four corner octagonal turrets, capped by plastered cupolas. These turrets rise slightly above the parapet walls and ribbed in typical Bengali fashion. Parapets are straight instead of the curvilinear cornice of pre-Mughal types. The eastern or main facade is visually divided into three sections. Each section contains an entrance arched doorway that correspond to the three domes above and adorned by cusped arches, each set off by a series of arched recessed niches.  The middle section is emphasized by a frame of slender, engaged columns, a raised cornice, and an elevated dome. There are three semi-octagonal mihrabs in the qibla wall; the central one is larger and the flanking ones narrower and dwarfish similar to the front façade.

The mosque was restored and repaired by the Department of Archaeology, Bangladesh and is now a protected monument.