Black-box models have demonstrated incredible performance and accuracy across various modeling problems and benchmarks over the past decade, from detecting objects in images to generating intelligent responses to user queries. Despite their impressive performance, these models suffer from a lack of interpretability, making it difficult to understand their decision-making processes and diagnose errors, which limits their applicability, especially in high-stakes domains such as healthcare and law. Explainable Artificial Intelligence (xAI) is a set of techniques, tools, and algorithms that bring transparency to black-box machine learning models. This transparency is said to bring trust to the users and, as a result, help deploy these models in high-stake decision-making domains. One of the most popular categories of xAI algorithms is local explanation techniques, where the information about the prediction of a black box for a single data instance. One of the most consequential open research problems for local explanation techniques is the evaluation of these techniques. This is mainly because we cannot directly extract ground truth explanations from complex black-box models to evaluate these techniques. In this thesis, we focus on a systematic evaluation of local explanation techniques. In the first part, we investigate whether local explanations, such as LIME, fail systematically or if failures only occur in a few cases. We then discuss the implicit and explicit assumptions behind different evaluation measures for local explanations. Through this analysis, we aim to present a logic for choosing the most optimal evaluation measure in various cases. After that, we proposea new evaluation framework called Model-Intrinsic Additive Scores (MIAS) for extracting ground truth explanations from different black-box models for regression, classification, and learning-to-rank models. Next, we investigate the faithfulness of explanations of tree ensemble models using perturbation-based evaluation measures. These techniques do not rely on the ground truth explanations. The last part of this thesis focuses on a detailed investigation into the faithfulness of local explanations of LambdaMART, a tree-based ensemble learning-to-rank model. We are particularly interested in studying whether techniques built specifically for explaining learning-to-rank models are more faithful than their regression-based counterparts for explaining LambdaMART. For this, we have included evaluation measures that rely on ground truth along with those that do not rely on the ground truth. This thesis presents several influential conclusions. First, we find that failures in local explanation techniques, such as LIME, occur more frequently and systematically, and we explore the mechanisms behind these failures. Furthermore, we demonstrate that evaluating local explanations using ground truth extracted from interpretable models mitigates the risk of blame, where explanations might be wrongfully criticized for lacking faithfulness. We also show that local explanations provide faithful insights for linear regression but not for classification models, such as Logistic Regression and Naive Bayes, or ranking models, such as Neural Ranking Generalized Additive Models (GAMs). Additionally, our results indicate that KernelSHAP and LPI deliver faithful explanations for treebased ensemble models, such as Gradient Boosting and Random Forests, when evaluated with measures independent of ground truth. Lastly, we establish that regression-based explanations for learning-to-rank models consistently outperform ranking-based explanation techniques in explaining LambdaMART. Our conclusion includes a mix of ground truth-dependent and perturbation-based evaluation measures that do not rely on ground truth.