In this dissertation, we explore how to improve scalability of blockchains while maintaining their fundamental premise of decentralization. Scalable blockchains are capable of delivering a target throughput and latency in the presence of increasing workload. To this end, first we present Bitcoin-NG, a new blockchain protocol designed to provide scale for services involving frequent, high-volume interactions. This Byzantine fault tolerant blockchain protocol is robust to extreme churn and shares the same trust model as Bitcoin. We experimentally demonstrate that Bitcoin-NG scales optimally, with bandwidth limited only by the capacity of the individual nodes and latency limited only by the propagation time of the network. Then, we examine the scalability challenges arising from proliferation of blockchain services. In particular, we observe that due to inherently single-service oriented blockchain protocols, services can bloat the existing blockchains, fail to provide sufficient security, or completely forego the property of trustless auditability. We introduce Aspen, a sharded blockchain protocol that securely scales with increasing number of services. Aspen enables service integration without compromising security -- leveraging the trust assumptions -- or flooding users with irrelevant messages. Finally, we provide the means to assess the viability of different scaling solutions. We develop and utilize custom metrics for evaluating performance and security of blockchain protocols. Moreover, we design tools and techniques for measuring decentralization in operational blockchain systems, demonstrating their use in a comparative study of decentralization in Bitcoin and Ethereum.