Gateway tells the story of Robinette (Bob) Broadhead's adventures in a space station that had been abandoned millions of years ago by a mysterious alien race. From this station, prospectors launch themselves into space via Heechee ships that take them to an unknown location where they will hopefully find priceless artifacts, but are more likely to find danger and death. Bob finds his way to Gateway after winning the lottery. While there, he falls in love with a fellow prospector, Karla, who, like Bob, is too scared to actually take a prospecting trip (though by the time he meets her, Karla has already taken 3 trips without major success).

Eventually Bob gets up the nerve to take a trip, but they aren't successful. One of their members goes crazy, and they are forced to tie him up for the trip back. After a fight with Karla (in which Bob attacks her violently), he decides to take a solo trip, only to be taken to Gateway Two, a second space station that had been discovered previously, making the trip a pointless endeavor for Bob. He gets back to Gateway, where he learns that his last trip has taught the corporation that runs Gateway how to pick a specific location on a trip. This allows them to set up a special assignment where they will send 2 Fives (five man ships) to the same location. Bob is on one ship and Karla (having returned to Gateway and reunited with Bob) is on the other.

Unfortunately when they arrive, they find themselves at a black hole. In order to try to survive, they move everything to one ship and are going to blow them apart to create the force they need to escape the black hole"s pull and return to Gateway. During the process of moving between ships, Bob gets trapped in the doomed ship. Just before they are going to blow them apart though, a member of the other ship says "No! No! Wait"¦." Though it is not stated explicitly, it seems that they had somehow got into the wrong position, resulting in the ship with the 9 crewmen being sent into the black hole, and Bob's ship being the one that is freed and returns to Gateway. Though Bob feels guilty about their deaths, it is not clear if he is the one who caused the ships to separate or if someone on their end set off the explosion. Still, Bob admits that he was going to cause it to go off, so even if he wasn't the direct cause in his mind he did kill the other crewman (and Karla). In fact, he claims his is still killing them because they are in the pull of the black hole, and thus Karla is still dying for eternity. In the end, Bob becomes exceedingly wealthy and lives his life of opulence back on Earth.