Construit en 1855 par Faidherbe, un officier de l’armée française, le Fort de Médine est le premier dispositif militaire dans la conquête du Soudan Français. Sa position stratégique sur le fleuve Sénégal permettait non seulement de surveiller la région déjà soumise entre Bakel (au Sénégal) et la ville de Médine, mais aussi de l’utiliser comme tête de proue pour la conquête des vastes territoires compris entre les bassins du Sénégal et du Niger. Le 20 avril 1857, environ deux ans après la construction du fort, El Hadj Omar Tall mit le siège devant Médine jusqu’au 18 juillet 1857, date à laquelle Faidherbe débarqua avec ses troupes pour sauver la ville. A la même occasion, Médine devenait le siège de l’administration coloniale. L’ouvrage comprend un grand bâtiment à deux niveaux (le mess des officiers) et des structures annexes (la poudrière, la prison et l’Ecole des Otages), le tout entouré d’une imposante muraille en pierres.