In this paper, a descent-ascent principle based heuristic optimization algorithm for the solution of the well-known combinatorial problem—the quadratic assignment problem—is introduced and investigated. The idea of the algorithm is based on the non-greedy exploration of the set of solutions, where the improving operations (moves) are combined with specific perturbations (mutations) of solutions. The extensive computational experiments with the proposed algorithm have been carried out to evaluate the performance of the algorithm. The results from the experiments demonstrate that our algorithm is capable of achieving high quality solutions within efficient execution time.