This paper proposes the novel application of matching markets with contracts for electric vehicle smart charging. The flexibility inherent in electric vehicle charging presents the new opportunity for automation and coordination to shape overall demand. Mechanisms that incentivise coordination are a promising approach for integrating the individual preferences and energy requirements of electric vehicle owners. However, these mechanisms require careful design, since they directly influence power system operation. This paper proposes a new market design, allowing owners of electric vehicles and aggregators to competitively negotiate contracts specifying the time and price of charging at discrete power levels. It is shown that the agents’ preferences over contracts satisfy the condition of substitutability, establishing the existence of a stable outcome – an agreed set of contracts no group of agents wish to mutually deviate from. A distributed price-adjustment process is then presented for finding stable outcomes, which only requires local agent decisions and agent-to-agent negotiation. An advantage of the proposed market design is that contracts specify discrete charging power levels, rather than requiring continuously controllable charging powers. This makes it suitable for standard charging infrastructure, and could potentially increase efficiency compared with strategies that operate chargers at low power levels.