Edge computing moves the computation closer to the data and the data closer to the user to overcome the high latency communication of cloud computing. Storage at the edge allows data access with high speeds that enable latency-sensitive applications in areas such as autonomous driving and smart grid. However, several distributed services are typically designed for the cloud and building an efficient edge-enabled storage system is challenging because of the distributed and heterogeneous nature of the edge and its limited resources. In this paper, we propose EdgeKV, a decentralized storage system designed for the network edge. EdgeKV offers fast and reliable storage, utilizing data replication with strong consistency guarantees. With a location-transparent and interface-based design, EdgeKV can scale with a heterogeneous system of edge nodes. We implement a prototype of the EdgeKV modules in Golang and evaluate it in both the edge and cloud settings on the Grid'5000 testbed. We utilize the Yahoo! Cloud Serving Benchmark (YCSB) to analyze the system's performance under realistic workloads. Our evaluation results show that EdgeKV outperforms the cloud storage setting with both local and global data access with an average write response time and throughput improvements of 26% and 19% respectively under the same settings. Our evaluations also show that EdgeKV can scale with the number of clients, without sacrificing performance. Finally, we discuss the energy efficiency improvement when utilizing edge resources with EdgeKV instead of a centralized cloud.