Machine Learning algorithms usually make decisions without providing any explanations on how they were reached. As a result, such models are not understood and trusted by the users. Counterfactuals are user-friendly explanations that provide valuable information to determine what should be changed in order to modify the outcome of a black box decision-making model without revealing the underlying algorithmic details. We present a novel technique to obtain counterfactual explanations by solving an optimization problem when a k-Nearest Neighborhood classifier is employed in a binary classification. Results from artificial and real datasets demonstrate the validity of the proposal.