Machine learning is a cornerstone of modern decision-making systems, yet its inner workings often remain a mystery to human stakeholders. Bridging this gap requires clear, human-understandable explanations of how these models transform inputs into outputs. One effective approach for achieving this type of transparency is through counterfactual explanations. Counterfactuals inform users about what changes need to be made and why, offering recommendations on how to alter an undesired outcome into a desired one, which ultimately enhances the comprehensibility and reliability of machine learning models. In this work, we propose TS-NUC, a novel model-agnostic counterfactual generation approach dedicated to the domain of time series classification. Our approach consists of a pre-trained LSTM-Autoencoder which generates the latent representation of a time series instance. By optimizing the latent representation, guided by the user-provided target class latent cluster, TS-NUC is capable of generating high-quality counterfactual explanation. Through extensive experiments on a total of 5 datasets from the UCR archive and performance comparison with latest state-of-the-art approaches on three popularly used evaluation metrics, namely Validity, Proximity and Compactness, we show that our approach produces comparable and better results.