Fürstbischof Clemens August von Bayern regierte das Hochstift Paderborn von 1719 bis 1761. Im Zuge der umfangreichen Barockisierung der Schlossanlage entstand der Marstall in den Jahren 1729 bis 1732/33. Die Bauleitung übertrug der Fürstbischof dem Hof- und Landbaumeister Franz Christoph Nagel.

Nach der Errichtung der preußischen Garnison in Neuhaus diente der Marstall von 1820 bis 1945 als Kavalleriegebäude. Von 1945 bis 1990 nutzten britische Militäreinheiten den Marstall. Die Stadt Paderborn erwarb 1991 das Gebäude und führte eine umfangreiche Restaurierung durch.

Der in Nordwestdeutschland in seiner Art und Größe einmalige Bau bot im Erdgeschoss Platz für über 100 Pferde. Der Mittelbau und die beiden angrenzenden Viertelbögen dienten als Wagenremisen. Im Obergeschoss des nördlichen Flügelgebäudes wohnten neben anderen der Baumeister Nagel und der Hofgärtner Hatzel.
Im Rahmen der Landesgartenschau 1994 wurden im Marstall das Historische Museum und das Naturkundemuseum eingerichtet.