Script was in the first version of Bitcoin. Satoshi developed Bitcoin in private before releasing the fully-usable Bitcoin 0.1, and he said very little about his thought-process, so we'll probably never know exactly why many things were done the way they were.
Script had several serious bugs when Bitcoin was first released, and some bugs still exist. It's clear that Satoshi didn't thoroughly test Script before releasing Bitcoin. And while it contains a lot of complexity, it is still too incomplete for most opcodes to be of any real use. In light of this, it's often speculated that Script was something of an afterthought. Perhaps Satoshi's design originally sent bitcoins only directly to public keys, but when adding support for Bitcoin addresses and thinking about future transaction types, he realized that a scripting language would be useful for forward-compatibility.
A stack-based language is the natural choice here. Script processing is dead simple and very fast: just keep reading opcodes from the script and evaluating them until the script is complete. Each opcode is pretty much self-contained. It's also easy to analyze scripts due to the fact that everything to the right of a certain point in a script can be considered a function. You can know for sure that any scriptPubKey that starts with OP_RETURN will always fail validation, and that any script which ends with
<pubKey> OP_CHECKSIG will always require the signature of that public key, regardless of what the rest of the script contains.
This functional aspect of Script was especially important when scripts were still evaluated by directly concatenating the scriptSig and scriptPubKey instead of evaluating them separately as is done today. In theory, you could put anything in the scriptPubKey and be sure that no matter what was in the scriptSig, your scriptPubKey would behave as a function taking an appropriate number of arguments from the stack. However, the opcode OP_RETURN originally just caused the script to end early instead of fail, so you could steal anyone's bitcoins by simply using the scriptSig
OP_TRUE OP_RETURN. It was also possible to put a pushdata opcode right at the end of a scriptSig to turn the entire scriptPubKey into a constant (which evaluates to true). Satoshi fixed these bugs by changing the behavior of OP_RETURN to cause the transaction to immediately fail and making it so that scriptSig and scriptPubKey are evaluated in two separate steps.