Den Anfang aber sollte man sich auf keinen Fall entgehen lassen. Die erst kürzlich vollkommen neugestaltete Abteilung zu Stein- und Römerzeit schildert die in Grundzügen ja bekannte Geschichte so anschaulich und gleichzeitig so kompakt, dass sie sich nicht nur für Familien mit Kindern empfiehlt, sondern auch Erwachsenen einen neuen Zugang ermöglicht. So veranschaulicht eine große Schautafel den Zeitverlauf anhand von Generationen: Die Ahnenreihe von 40 Großmüttern reicht bereits zurück bis zur Zeit Karls des Großen, 69 Großmütter sind es bis zur Zeit Cäsars usw. Auch die Vielzahl der eingesetzten Medien sorgt für Abwechslung: So die klassische Vitrine mit gut ausgeleuchteten Originalexponaten (etwa zum Umgang mit Verstorbenen in der Bronzezeit) oder Stimmung schaffende Wandfotos, so Modelle – etwa das Modell eines Lagerplatzes steinzeitlicher Menschen oder das eines Rentierlagers, die erst vor kurzem produziert wurden und daher den neuesten Stand wissenschaftlicher Kenntnis verarbeiten – oder die Multimediapräsentation im seit langem bestehenden Diorama des Kesslerlochs: Man lernt die Nutzung dieser Höhle im Ablauf der Zeiten kennen und betrachtet fasziniert die Demonstration der Durchschlagskraft, die die neu erfundene Speerschleuder besaß. Für alle Hundefreunde: Hier fand man den Knochen, der als ältester Beleg für die Haltung von Hunden gilt. Auch Videos gibt es in großer Zahl. Sie präsentieren teils Details der ausgestellten Originalexponate, teils zeigen sie die Archäologen bei der Arbeit und führen den Besucher damit in die Ausgangssituation der Objekte zurück. Letzteres gilt auch für schlitzartig wirkende horizontale Vitrinen, in denen die typischen Fundstücke der jeweiligen Zeit zusammengeschüttet sind: Steine und Klingen aus Silex in der Jungsteinzeit, Scherben und Werkabfälle in der Bronzezeit usw. Die Einfälle der Ausstellungsmacher garantieren dem Betrachter immer neue Blicke, und die knappen, aber sehr informativen Texte stillen seinen Wissenshunger.
Die Vielfalt der Medien setzt sich in der Römerzeit fort, die Texte stellen die Exponate gekonnt in ihren jeweiligen historischen Kontext, unaufdringlich, aber informativ. Hinzu kommen Originale wie Gefäße oder ein Fußbodenmosaik aus der damaligen römische Kleinstadt Iuliomagus. Herausragend ist eine Glasschale aus Stein am Rhein, die eine Jagdszene zeigt. Auch hier ermöglicht es ein Video, Details zu studieren; gleichzeitig erläutert es die Technik, die zur Herstellung der Schale verwandt wurde.
Den Übergang ins Frühmittelalter begleiten zeitgenössische Zitate. Im Kontext der Völkerwanderungszeit wird etwa Salvian von Marseille (um 400–480) zitiert: „Einst waren die Römer die Stärksten, jetzt sind sie ohne Kraft“. Ambrosius von Mailand (339–397) meinte gar: „Das Ende der Welt hat uns erreicht.“ Das Museum ist verwinkelt gebaut, nicht zuletzt, weil es immer wieder auch originale Teile des Klosters zu Allerheiligen in den Ausstellungsrundgang integriert, etwa die Johanneskapelle aus der Zeit des ersten Klosterbaus (1049–1064) mit ihren romanischen Fresken im Chorgewölbe. Dies weckt Neugier und eröffnet zudem Ausblicke in die anmutigen Innenhöfe, die sich beim Weitergehen auftun: in einem blickt man das frühere Wohngebäude des Abts und den mit romanischen Säulchen gesäumten offenen Gang in der ersten Etage, der die Wohnräume des Abts mit denen seiner Gäste verband; oder man erhascht einen Blick auf den Kreuzgang, an den sich ein historischer Kräutergarten anschließt, in dem man sich, wie in den anderen Innenhöfen, bei schönem Wetter allzu gern aufhält. In der ebenfalls in den Rundgang integrierten Eberhardskapelle vom Ende des 12. Jahrhunderts lassen sich Wandmalereien bewundern. Vor allem aber sind hier Grabmäler aufgestellt, die 1921 als spektakulärer Fund unter dem Bretterboden des Kirchenschiffs entdeckt wurden, wo man sie 1750 versenkt hatte. Sie zählen zu den frühesten Grabmälern mit lebensgroßen Figurenund erinnern an zwei Nellenburger Grafen. Diese sind in zeittypische Gewänder gehüllt. Der ältere, Eberhard (1010/15–1078/79), der Stifter des Klosters, trägt ein Kirchenmodell; der jüngere, Burkhart, hält ein Bäumchen mit Wurzelballen in den Händen als Symbol für die Eigentumsübertragung, denn die Nellenburger Grafen verzichteten 1080 auf die Besitzansprüche am Kloster und schenkten diesem die Stadt Schaffhausen samt all ihren Rechten.
