Nach dem Tod von Georg von Dachsberg 1423 ging laut Testament die Herrschaft über Rappottenstein an die Herren von Starhemberg über. Der letzte Dachsberger hatte seine Enkel Caspar und Gundakar von Starhemberg zu Erben eingesetzt, doch waren diese beiden bereits 1418, also fünf Jahre vor ihrem Großvater, gestorben. So scheinen daher von 1423–1428 Johann IV. und Rüdiger VII. von Starhemberg als Inhaber der Herrschaften Rappottenstein und Arbesbach auf. Es dürfte sich dabei um Nachkommen der vom Testament ursprünglich Begünstigten handeln.
Die Starhemberger leiten ihren Namen vom Schloss Starhemberg ab, das sie um 1176 bei Lambach in Oberösterreich erbauten. Von 1428 bis 1430 scheinen die Brüder Rüdiger VII. und Gundakar IX. von Starhemberg als Herren von Rappottenstein auf. Sie wurden von Herzog Albrecht V. belehnt und erweiterten 1428 ihren Besitz durch den Zukauf von Marbach und Rottenbach.
1439 wird die Pfarre Rappottenstein von den Starhembergern verliehen. Im Jahre 1430 starb Gundakar IX. Ab diesem Jahr ist also Rüdiger VII. Alleinbesitzer. Er gehört zweifellos zu den bedeutendsten Männern, die jemals über Rappottenstein herrschten. Rüdiger war ein treuer Anhänger Friedrichs III. Der Kaiser schätzte ihn sehr hoch und verlieh ihm eine Reihe wichtiger Staatsämter. Rüdigers Belehnung mit Rappottenstein erfolgte 1455. Er besaß aber auch noch „Antschau samt allen Gütern, Zehenten zu Prannt, Werssenslag, Zwinssen, Aichorns, Mitlberg, Royten u.a.“. Ferner übte er in seinem Herrschaftsbereich die Landgerichtsbarkeit aus. Als einer der wenigen kaisertreuen Adeligen (Friedrichs III.) hatte dieser Starhemberger oft Gelegenheit, seine Treue zum Herrscher unter Beweis zu stellen. So focht er manchen harten Strauß gegen den böhmischen Adeligen Johann von Sternberg aus, der 1471 sogar Ottenschlag besetzt hatte, und nahm 1474 das von Böhmen und Ungarn schwer bedrängte Stift Zwettl unter seinen Schutz, wobei es ihm gelang, den Feinden des Stiftes großen Schaden zuzufügen.
Die vielen Händel, in die dieser streitbare Mann verwickelt war, bedingten oft eine lange Abwesenheit von seinem Besitz. Diesen Umstand machte sich einer seiner räuberischen Standesgenossen, ein Ritter namens Plaz, zunutze, indem er die zeitweise unbeschützten Untertanen des Starhembergers plünderte.
In den Jahren 1430-1440 ließ Rüdiger VII. die Pfarrkirche in Schönbach erbauen. Es muss diesem tatkräftigen Mann also gelungen sein, seinem Herrschaftsbereich in diesen bewegten Zeiten verhältnismäßig große Ruhe und Sicherheit zu gewähren.
Aus dem Jahre 1477 stammt eine Urkunde, die für Rappottenstein von Bedeutung ist: Ulrich Puchler, Pfleger zu Rappottenstein, siegelte in diesem Jahre einen Kaufvertrag, nach dem der Rappottensteiner Bürger Peter Lebzelter gewisse Lehen in Rappottenstein erhielt. (Noch heute heißt der betreffende Bauernhof „Lebzelterhof“.) Weil hier also von einem „Bürger“ Rappottensteins die Rede ist, darf man schließen, dass der Ort damals bereits das Marktrecht besaß. Pfarrer Plesser nimmt an, es stamme schon aus dem 14. Jahrhundert, also noch aus der Zeit der Dachsberger.
Im Jahre 1477 war Rüdiger von Starhemberg zusammen mit anderen österreichischen Adeligen am Abschluss eines Waffenstillstandes mit den Böhmen beteiligt, der vom 31.12.1477 bis St. Georg 1488 währte. In der Urkunde wird Rappottenstein ausdrücklich erwähnt. Nach Ablauf dieses Waffenstillstandes fielen die Böhmen wieder im Waldviertel ein und verheerten das Land in entsetzlicher Weise. So wird berichtet, dass Petrus von Sternberg gegen 3.000 Haustiere als Beute nach Böhmen verschleppte. Rüdiger VII. starb hoch betagt im Jahre 1480, nachdem er nicht weniger als 57 Jahre die Herrschaft über Rappottenstein zum Wohle seiner Untertanen und zur Ehre und zum Nutzen seines Geschlechtes ausgeübt hatte.
Wahrscheinlich wurde von ihm auch die Erweiterung der romanischen Pfarrkirche zu einer dreischiffigen gotischen Anlage durch Anbau von niedrigeren Seitenschiffen durchgeführt. Die romanischen Langhausmauern wurden beiderseits von Spitzbogenöffnungen durchbrochen, die Schiffe erhielten Netzgewölbe. Im nördlichen Seitenschiff wurde eine Gruft erbaut, ein Gegenstück zu der im Süden liegenden Dachsbergergruft. Am 26.12.1481 schreibt Rappottenstein-Hans Kutnbaum, Pfleger zu Neusiedl, der Kaiser habe ihm befohlen, „meinem gnedigen herrn, herrn Ulrichen sein pruedern und vettern von Starhemberg das geslos Rapotenstain abzutreten“.
So ist es zu erklären, dass mit Georg von Starhemberg, dem einzigen Sohn Rüdigers VII., gleichzeitig ein Vetter Georgs, Ludwig von Starhemberg, als Besitzer aufscheint. Von 1481 bis 1491 saßen diese beiden Starhemberger also gemeinsam auf Rappottenstein. Als Georg von Starhemberg 1491 starb, übte Ludwig die Herrschaft alleine aus, und zwar bis zum Jahre 1513. Ludwig von Starhemberg ging im Jahre 1487 mit den Ungarn, die ja damals einen großen Teil Österreichs besetzt hielten und von 1486 bis 1489 eine starke Besatzung von 200 Mann im Stift Zwettl liegen hatten, wegen der Feldbestellung und Ernteeinbringung einen Waffenstillstand ein. Während seiner Regierungszeit wurde die Pfarrkirche in spätgotischem Stile umgebaut.
Nach Ludwig von Starhemberg folgte von 1513 bis 1531 dessen Bruder Bartholomäus. Dieser Starhemberger wurde dadurch bekannt, dass er im Jahre 1524 als einer der ersten österreichischen Adeligen zum Protestantismus übertrat. Er begünstigte die Verbreitung der neuen Lehre in jeder Weise, obwohl er vorerst den katholischen Pfarrer auf der Pfarre Rappottenstein beließ. Bartholomäus I. stand mit Luther sogar im Briefwechsel. Von 1531 bis 1533 scheint Hanns VI., ein Sohn des Bartholomäus, als Besitzer der Burg auf. Vom 21. Mai 1531 datiert eine alte Gültanlage des Erasmus von Starhemberg, in der die Zahl der Untertanen der Herrschaft Rappottenstein mit 500 angegeben wird (Gültbuch im Niederösterreichischen Landesarchiv).
Nach Hanns VI. teilten sich zwei Erben den Besitz, und zwar sein Sohn Erasmus I. und sein Neffe (?) Hanns VII. Sie herrschten von 1533 bis wahrscheinlich 1555 und machten sich durch den Ausbau der Burg, der in die Jahre 1548–1550 fällt, verdient. Die Burg dürfte damals ihr heutiges Aussehen erhalten haben. Es entstand nicht nur der große Westtrakt (Südtrakt) mit seinen Arkadengängen im Innern des Burghofes, sondern auch der Uhrturm. Die äußere Umfassung wurde um den großen ersten Hof erweitert, wobei die beiden runden Einfahrtstürme entstanden. Auch das Brauhaus, an dem die Jahreszahl 1548 zu sehen ist, fällt in diese Bauperiode.
Der letzte Starhemberger Paul Jakob verkaufte 1556 die Herrschaft an die Herren von Landau.