This paper presents a novel approach for designing and optimizing maintenance service contracts through the application of mechanism design theory. When offering a contract to its customer, the maintenance service provider seeks to specify contract terms - such as price, service features and incentives - that maximize the provider's profit, satisfy customer needs, allocate risks effectively and mitigate moral hazards. Optimal contract design has to account for asymmetric information and uncertainties associated with customer characteristics and behaviors. We illustrate our mechanism design approach by applying it to the contract design challenge of a gas turbine manufacturer, which also provides maintenance services for its aircraft engines. In our solution approach, we compute an optimal set of contracts. The entire set is presented to the customer and is designed such that the customer will accept one of the contract alternatives without negotiations. In addition to eliminating the costs and delays associated with negotiations, this approach also reveals the customer's private information to the service provider, which the provider can use to its benefit in maintenance management and future contract renewals. Furthermore, we design and incorporate win-win incentive mechanisms into the contracts, which reward the customer for actions that reduces maintenance costs. We present a deterministic and a stochastic mechanism design model, the latter accounting for uncertainties associated with customer actions, engine performance, and maintenance costs during the contract execution phase.