The Arab Fort (also called the old fort, and by its local name Ngome Kongwe) is next to the House of Wonders. It is a large building, with high, dark-brown walls topped by castellated battlements. It was built between 1698 and 1701 by the Busaidi group of Omani Arabs, who had gained control of Zanzibar in 1698, following almost two centuries of Portuguese occupation. The fort was used as a defence against the Portuguese and against a rival Omani group, the Mazrui, who occupied Mombasa at that time.

The fort was constructed by the Busaidi Omani Arabs on the site of a Portuguese church which had been built between 1598 and 1612. In the main courtyard, remnants of the old church can still be seen built into the inside wall. In the 19th century the fort was used as a prison, and criminals were executed or punished here, at a place just outside the east wall. The Swahili word gereza, meaning prison, is thought to be derived from the Portuguese word ireja, meaning church.

In the early 20th century, the fort was also used as a depot for the railway line which ran from Zanzibar Town to Bububu. In 1949 it was rebuilt and the main courtyard used as a ladies' tennis club, but after the 1964 Revolution it fell into disuse.

Today, the fort has been renovated, and is open to visitors. It is possible to reach the top of the battlements and go onto the towers on the western side. In 1994 a section was turned into an open-air theatre. The development was imaginative yet sympathetic to the overall design and feel of the original building: seating is in amphitheatre style, and the fort's outer walls and the House of Wonders form a natural backdrop. The theatre is used for performances of contemporary and traditional music, drama and dance. The fort also houses a tourist information desk, with details on performances in the amphitheatre and other events around town, plus a selection of books for sale and a range of tour company leaflets to browse. There are also several spice and craft shops, a pleasant café, and remarkably some very clean public toilets. And don't miss the Tower Workshop in the west tower, where local artists create and display their works (more details are given in the Shopping section). Even if historical ruins don't interest you, the Fort is well worth a visit. With so many attractions and facilities, it's easy to spend quite a few hours here.