Storage Grid is a new model for deploying and managing the heterogeneous, dynamic, large-scale, and geographically distributed storage resources. This chapter discusses the challenges and solutions involved in building a Service Oriented Storage (SOS) Grid. By wrapping the diverse storage resources into atomic Grid services and federating multiple atomic Grid services into composite services, the SOS Grid can tackle the heterogeneity and interoperability. Peer-to-peer philosophy and techniques are employed in the SOS Grid to eliminate the system bottleneck and single point of failure of the traditional centralized or hierarchical Grid architecture, while providing dynamicity and scalability. Because Grid service is not designed for critical and real-time applications, the SOS Grid adopts Grid service to glue the distributed and heterogeneous storage resources, while using binary code to transfer data.