While writing the metric for AdS Space, why are we starting with a five dimensional Flat space and embedding a hyperboloid in it?
Does it have to do with the fact that the cosmological constant being negative?
Embedding the AdS 4D spacetime as a hypersurface in a 5D manifold is just a convenient way of studying it. There is no physical meaning to the 5D manifold - it is just a mathematical device.
Any 4D spacetime can be embedded in a manifold of higher dimensionality, though it turns out to be surprisingly complicated to specify what dimensionality the manifold has to be. See this question in the Math Overflow for more on this.
So, no, the embedding is not specifically related to a negative cosmological constant. De Sitter space can be embedded in a 5D manifold in the same way, and indeed as Robert Greene's work tells us any spacetime can be embedded, though in general the dimensionality required will be higher than five.