Anfang des 11. Jahrhunderts wurde an Stelle der frühen Holzkirche der erste Steinbau auf dem Burgberg errichtet. Die einschiffige Saalkirche mit halbrunder Apsis war ca. 19 Meter lang und 9,50 Meter breit. Um 1035 wurde direkt vor der Nordostecke dieser Kirche eine hochgestellte Persönlichkeit bestattet. Die Grablege des 20 bis 30 Jahre alten Mannes war mit einer Umfassungsmauer und einer Sohle aus Steinpflaster ausgestattet. Die herausgehobene Stellung und Bauweise des Grabes lassen darauf schließen, dass hier ein Angehöriger der Vohburger Grafen bestattet wurde. Vielleicht starb mit ihm der alte Ortsadel aus. Seit 1040 waren die Grafen von Rott die neuen Herren auf der Vohburg. Kuno von Rott, seit 1059 Pfalzgraf, ließ wohl neben dieser ersten Steinkirche einen frühen steinernen Wohnturm als herrschaftlichen Wohnsitz errichten.
Nördlich dieses frühen Wohnturms konnten 32 Gräber des hochmittelalterlichen Friedhofes freigelegt werden, der von einer Mauer umgeben war. In den Gräbern lagen bis zu sechs Skelette übereinander, was für eine oberirdische Kennzeichnung der Grabstellen spricht. Die Untersuchung der Skelette ergab, dass im 11. Jahrhundert hier 13 Männer, 12 Frauen und 19 Kinder bzw. Jugendliche bestattet wurden. Den Holzspuren und den erhaltenen Nägeln nach zu urteilen, wurde etwa ein Drittel der Toten in einem Sarg bestattet, weitere sieben wurden wohl in ein Grabtuch gewickelt. Auffällig war, dass bei etwa der Hälfte der Gräber neben dem Skelett Kalksteine deponiert waren, bevorzugt in Höhe der Arme oder Beine, seltener im Kopf- und Fußbereich.
Kuno von Rott-Vohburg starb in der Schlacht ohne einen männlichen Erben zu hinterlassen. Über Kunos Witwe Elisabeth kam die Herrschaft Vohburg nach 1081 an den Pfalzgrafen Rapoto von Cham, der aber schon 1099 einer Seuche erlag. Elisabeth, nun zum zweiten Mal verwitwet, blieb anscheinend bis zu ihrem Lebensende die Besitzerin der Vohburg.