We consider the maintenance of single server queues in which the deterioration of a server is subject to random shocks. Shock arrivals deteriorate the server by a random amount. A maintenance policy is proposed whereby the server is repaired whenever its state is above a specified maintenance level. We present the system size distribution and sojourn time distribution. We derive the long run average cost, considering holding cost and repair cost. We analyze the proposed maintenance policy based on the cost analysis. (C) 2009 Elsevier Ltd. All rights reserved.