Before HTTP based services became predominant, there were several other systems which provided similar functions. In the Windows world, when COM was a popular component model, it was common to use DCOM, a binary RPC protocol over TCP which allowed you to call methods on COM objects in remote processes or remote machines. COM+ was an application server based on DCOM, allowing services to be registered, executed and managed. MSMQ was another option, a distributed, asynchronous queue system where one app could write to a queue to be picked up by the queue processing service.
I used these technologies, and others, to build distributed, service-oriented architectures back in the 90's. Other options existed even earlier. CORBA was similar to COM, less MS-centric, and application servers running CORBA components existed for various platforms.
SOA is about separating your applications into distinct, independent domains. It's similar to the Separation of Concerns principal in coding, but at the architectural level. And just like SoC doesn't rely on a specific technology or paradigm like OOP, so SOA doesn't rely on having Web-services or similar online RPC mechanisms. In fact, web services aren't "an implementation of SOA", as much as they're architectural components that can be used for SOA. The same WS technologies are often used as the back-end for straightforward client-server apps, after all.