Censored quantile regression models are very useful for the analysis of censored data when standard linear models are felt to be appropriate. However, fitting censored quantile regression is hard numerically due to the fact that the function that has to be minimized (Powell estimator) is not convex nor concave in regressors. The performance of standard methods is not satisfactory, in particular if a high degree of censoring is present. Usual approach in the literature is to simplify (linearize) estimator function and show theoretically that such approximation tends to good real optimal values. In this paper we suggest different approach, i.e., we solve directly nonlinear non-convex non differentiable optimization problem. Our method is based on variable neighborhood search approach, a recent successful technique for solving global optimization problems. Simulation results presented indicate that our new method can improve the quality of censored quantizing regressors estimator considerably. Moreover, an extramarital affairs example involving censored regression analysis is also used to illustrate the method.