Die Burg war der Stammsitz der 1129 erstmals erwähnten, später reichsunmittelbaren Herren von Heideck. Diese nannten sich bis 1169 Herren von Erlingshofen, seit 1156 saßen sie auch auf Burg Arnsberg und, als sie vor 1278 eine neue Burg (= Schlossberg) bei Heideck bauten, bezeichneten sie sich fortan als Herren von Heideck. Die Stammburg Erlingshofen zerfiel.
Die noch 1379 als „alter Burgstall“ bezeichnete Anlage, die zur bayerischen Herrschaft Arnsberg gehörte, baute 1381 Paul Stosser unter dem Namen „Stossenberg“ neu auf und trug sie den Herzögen von Bayern zu Lehen auf. Die seit 1246/59 genannten Stosser waren ursprünglich Dienstleute der Marschälle von Pappenheim und hatten Besitz in der Weißenburger Gegend. 1383 gab Hans Stosser die Veste an Herzog Stephan den Kneißel von Bayern-lngolstadt zurück, der sie den Absbergern von Rumburg zunächst verpfändete und schließlich 1409 verkaufte. Diese hatten die Burg bereits 1388 als Heiratsgut an die Schenken von Geyern weitergegeben, die hier eine Nebenlinie ihres Geschlechts begründeten. 1481 veräußerten die Schenken ihre Rechte an Stossenberg um 500 Gulden an Fürstbischof Wilhelm von Reichenau. Das Hochstift Eichstätt ließ die Burg verfallen.
Der paradoxe Name „Rundeck“ taucht erst 1801 auf.
