Erstmals wurde der Ort im Jahr 1255 als „Balneolum“ (Lateinisch für 'kleines Badehaus') erwähnt.
Am 1. Januar 1860 wurde die Stadt Paris erweitert, indem die angrenzenden Gemeinden angegliedert wurden. Dabei wurde ein Teil der Gemeinde Bagnolet zu Paris eingemeindet. Gleichzeitig wurde die Gemeinde Charonne aufgelöst und zwischen Paris, Bagnolet und Montreuil aufgeteilt. Bagnolet erhielt einen kleinen Teil des Gebiets von Charonne.
Als Grenzstadt zu Paris ist Bagnolet an den Boulevard périphérique angeschlossen. Die Autoroute A3 zweigt hier vom Périphérique ab und durchschneidet Bagnolet. Die Stadt ist außerdem durch die Station Gallieni an das Métro-Netz von Paris angeschlossen. Der Busbahnhof Paris-Gallieni liegt auf dem Gebiet der Gemeinde Bagnolet.