Beginning with the 6th game in the series, the beginning of the 'Kiseki games,'
Legend of Heroes: Trails in the Sky (Sora no Kiseki) [CURRENTLY ON PSP]
Legend of Heroes: Trails in the Sky Second Chapter [CURRENTLY BEING WORKED ON FOR PSP]
This is a duology about Joshua and Estelle.
Legend of Heroes: Trails in the Sky The 3rd [NOT BEING WORKED ON, BUT POSSIBLE IF SERIES SELLS WELL]
This is an epilogue with new story threads expanding into the rest of the series.
Legend of Heroes 7:
Legend of Heroes: Zero no Kiseki
Legend of Heroes: Ao no Kiseki
[NEITHER OF THESE BEING WORKED ON. NON-LOCALIZED PC VERSIONS EXIST SO ITS POSSIBLE IF SERIES SELLS WELL, BUT MAYBE ONLY ON PC]
This is a duology set in the Crossbell part of the same world as the Trails in the Sky. Considered by many to be even better than Sky at some points, as well as better gameplay wise.
Legend of Heroes 8:
Legend of Heroes: Trails of Cold Steel (Sen no Kiseki)
Legend of Heroes: Trails of Cold Steel II
[BOTH BEING WORKED ON FOR VITA ETC]
This is a duology? set in Erebonia and what we're talking about now.
Nayuta no Kiseki is a spinoff unrelated to any of this.