The hall of heroes will be opened the second star stone you find (the first opens the observatory portal). Both are available fairly early, once you get to Cyseal. One you can not miss if you follow the murder investigation; the other there could be a delay, if you hold off deciding something (reminiscent of a Divine Divinity quest, though there is no DD-like solution in D:OS) or advance the murder investigation too far and miss the first opportunity.
