Abstract Today’s power systems are experiencing a transition from primarily fossil fuel based generation toward greater shares of renewable energy sources. It becomes increasingly costly to manage the resulting uncertainty and variability in power system operations solely through flexible generation assets. Incorporating demand side flexibility through appropriately designed incentive structures can add an additional lever to balance demand and supply. Based on a supply model using empirical wind generation data and a discrete model of flexible demand with temporal constraints, we design and evaluate a local online market mechanism for matching flexible load and uncertain supply. Under this mechanism, truthful reporting of flexibility is a dominant strategy for consumers reducing payments and increasing the likelihood of allocation. Suppliers, during periods of scarce supply, benefit from elevated critical-value payments as a result of flexibility-induced competition on the demand side. We find that, for a wide range of the key parameters (supply capacity, flexibility level), the cost of ensuring incentive compatibility in a smart grid market, relative to the welfare-optimal matching, is relatively small. This suggests that local matching of demand and supply can be organized in a decentral manner in the presence of a sufficiently flexible demand side. Extending the stylized demand model to include complementary demand structures, we demonstrate that decentral matching induces only minor efficiency losses if demand is sufficiently flexible. Furthermore, by accounting for physical grid limitations we show that flexibility and grid capacity exhibit complementary characteristics.