In today's day and age where information is spread rapidly through online platforms, the rise of fake news poses an alarming threat to the integrity of public discourse, societal trust, and reputed news sources. Classical machine learning and transformer-based models have been studied extensively for claim verification, however, they are hampered by their reliance on static training data and cannot generalize on unseen headlines. To address these challenges, we propose our explainable solution, which leverages web-information retrieval techniques and Natural Language Inference models to verify the veracity of a news headline. We evaluate our solution on a diverse self-curated evaluation dataset spanning multiple news channels and domains. Our best-performing pipeline achieves an accuracy of 84.3% surpassing the best classical Machine Learning model by 33.3% and Bidirectional Encoder Representations from Transformers by 31.0%. Utilizing hardware accelerators our pipelines achieve end-to-end fact verification inference times ranging from 2.92-6.97 seconds. Our approach highlights the efficacy of combining dynamic information retrieval with Natural Language Inference to find support fora claimed headline in the corresponding externally retrieved knowledge. The respective code, dataset, and results of this study are available in our artifact: https://github.com/Arjun254/VERITAS-NLI.