Die Entstehung und die Geschichte von Vincennes ist eng mit der dortigen Burg, dem château de Vincennes, verknüpft. Im 12. Jahrhundert entschloss sich König Ludwig VII. von Frankreich, den Wald von Vincennes zum königlichen Jagdgebiet zu erklären, und ließ eine Burg erbauen. Durch die Jahre hindurch wurde diese immer wieder umgestaltet und ausgebaut. Die mittelalterlichen Gebäude sind die einzigen Bauwerke einer Königsresidenz aus dem Mittelalter in Frankreich. Weil dort mehrere Könige residierten, wird die Burg auch „Versailles des Mittelalters“ genannt.
Im Jahre 1162 ließ Ludwig VII. einen Teil des Waldes von Vincennes mit einer Mauer umgeben und einen Jagdpavillon darin errichten. Im 13. Jahrhundert begann König Philipp August mit dem Bau einer Burg, die unter Ludwig IX. fertiggestellt wurde. Von 1270 bis 1350 war die Burg der beliebteste Aufenthaltsort der französischen Könige. Zwei königliche Hochzeiten wurden im Schloss gefeiert (Philipp III. und Philipp V.) und zwei Könige starben dort (Ludwig X. und Karl IV.). Auch nach dem Hundertjährigen Krieg residierten Könige in Vincennes (besonders Ludwig XI., Franz I. und Heinrich II.). 1661 wurde in Vincennes ein Friedensvertrag zwischen dem Königreich Frankreich und dem Herzogtum Lothringen abgeschlossen. Auch verlegte Ludwig XIV. den Sitz des Ordre de Saint-Michel vom Mont-Saint-Michel hierher. Erst mit dem Tod Ludwigs XIV. 1715 wurde Vincennes als Residenz aufgegeben.
Im 18. Jahrhundert siedelten sich unterschiedliche Industriezweige im Schloss an (Porzellanmanufaktur, Fayencen-Maler und eine Waffenschmiede). Erst 1787 wurde Vincennes eine Stadt. Mit dem Neubau des Fort-Neuf (1841) wurde Vincennes Garnisonsstadt und zwischen 1817 und 1856 zählte man rund 4000 Einwohner. Im Jahre 1861 waren es bereits 5800.
