Το Φουστάτ ήταν η πρώτη αραβική πρωτεύουσα της Αιγύπτου. Ιδρύθηκε το 641 μ.Χ., αφού οι Άραβες κατέλαβαν την Αλεξάνδρεια. Οι Άραβες δεν ήθελαν η πρωτεύουσά τους να είναι τόσο μακριά όσο η Αλεξάνδρεια, γι' αυτό και έφτιαξαν το Φουστάτ, το οποίο ήταν πιο κοντά και βρισκόταν στην πλευρά του ποταμού Νείλου.
Η Φουστάτ έγινε μια όμορφη και ισχυρή πόλη για πάνω από 500 χρόνια, αλλά στη συνέχεια καταστράφηκε κατά τη διάρκεια ενός πολέμου, όταν ο βεζίρης της Σαουάρ διέταξε τον στρατό του να κάψει την πόλη. Ο Σαουάρ δεν ήθελε να καταλάβει κανείς άλλος την πόλη, γι' αυτό την έκαψε.
Σήμερα δεν έχουν απομείνει πολλά από το Φουστάτ, αλλά κάποια κτίρια μπορεί κανείς να δει στο Παλιό Κάιρο.