Originally Posted by Cygnus Q'ol
I had a horse. When I went into towns, he stayed near the stables.
I hate to say this because I hate using it. Fast Travel a time or two till it says "Your horse is in the stable"
I'm playing on Xbox too, and that how I got mine back. Unfortunately I fast traveled to a couple camps to get him back and he came back alright and was promptly killed by the bandits.