This article proposes a number of efficient heuristics for two versions of the Median Cycle Problem (MCP). In both versions the aim is to construct a simple cycle containing a subset of the vertices of a mixed graph. In the first version the objective is to minimize the cost of cycle and the cost of assigning vertices not on the cycle to the nearest vertex on the cycle. In the second version the objective is to minimize the cost of the cycle subject to an upper bound on the total assignment cost. Two heuristics are developed. The first, called the multistart greedy add heuristic, is composed of two main phases. In the first phase, a cycle composed of a limited number of randomly chosen vertices is constructed and augmented by iteratively adding the vertex yielding the largest cost reduction until either no further reduction is possible (for the first version) or the assignment cost is below the upper bound (for the second version). The second phase applies a number of improvement routines. The second heuristic is a random keys evolutionary algorithm. Computational results on a number of benchmark test instances show that the proposed heuristics are highly efficient for both versions of the problem, and superior to the only other available heuristic for these two versions of the problem. Median Cycle Problem (MCP). In both versions the aim is to construct a simple cycle containing a subset of the vertices of a mixed graph. In the first version the objective is to minimize the cost of cycle and the cost of assigning vertices not on the cycle to the nearest vertex on the cycle. In the second version the objective is to minimize the cost of the cycle subject to an upper bound on the total assignment cost. Two heuristics are developed. The first, called the multistart greedy add heuristic, is composed of two main phases. In the first phase, a cycle composed of a limited number of randomly chosen vertices is constructed and augmented by iteratively adding the vertex yield