Yes. Your entire deployment stack, including heroes, must move out of the fortress at their earliest opportunity. Once outside of the fortress, it is your choice how much of your heroes' movement stat to use and where they move.