De geschiedenis van het Kasteel Stein begint met Herman van Elsloo. In 1220 wordt hij in het oudste tot nu toe bekende document vermeld, als hij met toestemming van zijn leenheer Dirk van Heinsberg een derde van de Steinse tienden overdraagt aan de abdij Herckenrode bij Hasselt. Het stamhuis van de oudste heren van Stein is dus Elsloo. Herman is een jongere broer van Arnold van Elsloo, die zijn vader in de heerlijkheid Elsloo opvolgde. Herman heeft de heerlijkheid Stein als leengoed in beheer gekregen van de graaf van Loon en van de Heer van Valkenburg. In Stein heeft Herman ongetwijfeld een versterkt huis bezeten. Als kruistochtridder nam hij in 1218 deel aan de verovering van het Egyptische Damiate. In 1220 was hij terug in zijn heerlijkheid. Na Hermans overlijden volgt zijn zoon Arnold hem op en hij noemt zich in 1230 als eerste “Heer van Stein”. Na hem volgen nog vijf generaties van het geslacht van Stein.
De donjon is rond 1250 tijdens het leven van Arnold III ontstaan. Deze Arnold nam onder de graaf van Loon in 1288 deel aan de beroemde slag van Woeringen en werd daar tot ridder geslagen. Hij trouwde in Holland met Margaretha van Renesse, werd leenman van de Hollandse graaf Floris V. De herinnering aan deze Arnold leeft voort in Stein bij Gouda, dat naar hem vernoemd is.
Er zijn meerdere schenkingen bekend van Steinse tienden aan de abdij Herckenrode. Het mag dan ook niet bevreemdend klinken dat Margaretha van Stein is ingetreden in deze kloostergemeenschap en in 1303 abdis van deze abdij werd.
De laatste Arnold van Stein werd samen met de hertog van Brabant en tal van andere edelen bij de slag van Baesweiler gevangen genomen en door de hertog van Gulik gedurende een half jaar opgesloten in slot Nydeggen totdat voor hem een zwaar losgeld betaald was.