Service-oriented computing is an interesting paradigm not only for building business applications but also for scientific applications requiring a loosely-coupled communication system between its components. In particular, scientific applications involving symbolic computations that are both computational and data intensive have proved in the last years to be adequate for implementation in service-oriented architectures, mainly due to the standards promoted for communications or service discovery. This chapter discusses the main issues and problems encountered in the transition from the classical symbolic computations based on stand-alone computer algebra systems towards service-oriented symbolic computations, such as building services from legacy codes, discover, compose and orchestrate services, standardize the exchange data formats. Moreover, several new approaches to solve at least partially these transition problems have been recently implemented, tested and are revealed in this chapter.