Large-scale deployment of renewable energy sources brings new challenges for smart grid management requiring the development of decentralized solutions and active participation of prosumer and non-grid-owned assets. Local energy flexibility markets can help in monitoring energy flows, motivate changes in prosumers’ energy supply and demand, achieving local energy balance, and optimization of electricity flows. In this paper, we propose a blockchain-based decentralized energy flexibility market enabling small-scale prosumers to trade in a peer-to-peer fashion their flexibility in terms of load modulation concerning the baseline energy profiles. We have defined an energy flexibility token for digitizing the flexibility of prosumers allowing to be traded on the market as an asset and self-enforcing smart contracts for decentralized market operation including functions such as the placement of flexibility bids/offers, trading session management, or energy and financial settlement of energy flexibility transactions. For matching the flexibility bids and offers, a solution based on a greedy heuristic and a bipartite graph is proposed for minimizing the number of flexibility transactions and reducing the blockchain-associated costs, while Oracles are used to assure its secure integration with the blockchain. The blockchain-based flexibility market was validated with the help of the Terni city Distribution System Operator, showing promising results in enabling the self-consumption of renewable energy generated in a small scale urban micro-grid considering live energy monitoring data, and in assuring the local balancing of the demand side in a simulated environment considering many market participants and historical energy data.