With the rapid advancement of Earth Observation systems, Earth Observation data has been collected and accumulated at an unprecedented fast rate. Earth Observation Big Data emerged with new opportunities for human to better understand the Earth systems, but also pose a tremendous challenge for efficiently transforming Big Data into Earth Observation Big Value. Targeting on this challenge, a well-organized data index is a key to enhance the “Data-Value” transformation by accelerating the access to data. Although various data indexing approaches have been proposed with different optimization objectives, literature shows that there are still apparent limitations for Earth Observation data indexing. This paper aims to build a spatiotemporal indexing for Earth Observation Big Data. Specifically, a) to support various Earth Observation Data Infrastructures, we adopt an indexing framework to efficiently retrieve data with various textual, spatial and temporal requirements; b) a distributed indexing structure is designed to improve the index scalability; c) data access pattern is integrated to the indexing algorithm for both spatial and workload balancing. The results show that our indexing approach outperforms traditional indexing approaches and accelerates the access to Earth Observation data. We envision that data indexing will become a key technology that drives fundamental Earth Observation advancements in the Big Data era.