Saying that there was no space is closer to reality, but the truth is that the universe expanded out of a point with zero space at the beginning of time; there is no void that the universe is expanding into because it is space itself that is expanding, carrying all of the matter and energy within the universe with it.

A good way to think of it is blowing up a balloon with cotton balls glued to the surface. The cotton balls are all of the matter, energy, etc., while the rubber of the balloon is space-time. As the balloon expands, the balls of cotton get farther and farther apart, because the rubber is stretching.