Constructed during the reign of Emir Abu Iqal (838-841), Masjid Bu Fatata served as a model for the Great Mosque of Sousse, built twenty years later. Although no conclusive evidence exists, scholars speculate that the mosque was built for the private use of the Emir.
The mosque is rectangular in plan, comprising a small square prayer hall preceded by a porch. The dimensions of the prayer hall are roughly eight by eight meters: three barrel-vaulted naves cross three bays, creating a grid of nine smaller squares within the plan. Four central rectangular piers stand at the four corners of the central square, and additional structural piers protrude from the walls. Horseshoe arches supporting the roof rest on the rectangular piers. These arches are repeated on the exterior of the prayer hall, where they support the vaults of the entrance porch. A later addition constructed to the east of the prayer hall pierces its east wall with two openings to allow for access. A minaret over the northwest corner of the prayer hall was also added at this time.
The triple-arched façade of the mosque formed by the porch is topped with Kufic inscriptions that include the date of construction. The mihrab, set in a "cul-de-four" niche, is flanked by two small columns. The floor level of the prayer hall today is slightly raised in comparison to the original construction.