I am not 100% sure, but I think you have to multiclass into it. Take Ace Pilot for example, if in the Navy service you build up you character and get all the prerequisites. Then multiclass into it. You still roll on the navy tables but apply earned XP's to the Ace Pilot class.
I think the general idea was that a prestige class would be one entered into in actual gameplay. However it can be done in prior history if when you meet the prerequisites you continue prior history in the prestige class under the multiclassing rules. Remember, "Class" and "Prior History" while sharing names do not have to be matched. You can be a "Traveller" (prior history) with "Rogue" (class) interests for example.
For example, the prestige class TAS Field Reporter is available once you get the required P/Journalism 4+, Gather Info 8+, and T/Electronics 4+ (minimum Class level 5). Then you are able to multiclass into the prestige class and continue prior history generation from there.
EDIT Had to step away from the keyboard in the middle of answering and came back to finish and find I'm beaten to the answer.