The Terror Star is listed as a fourth type of starbase once you have the first tech finished.  If you don't see it when you hit Construct then a.) you're playing in campaign, and it won't be available at the bit you're on, or b.) you're in a Sandbox game and the United Planets have outlawed Terror Stars, making it impossible to build them unless you leave the UP, or c.) It's a bug.

It doesn't start that way; you must have simply clicked through it.

We've all done it-even me, once or thrice.