In recent years many Life Cycle Assessment (LCA) studies have been conducted to quantify the environmental performance of products and services. Some of these studies propagated numerical uncertainties in underlying data to LCA results, and several applied Global Sensitivity Analysis (GSA) to some parts of the LCA model to determine its main uncertainty drivers. However, only a few studies have tackled the GSA of complete LCA models due to the high computational cost of such analysis and the lack of appropriate methods for very high-dimensional models. This study proposes a new GSA protocol suitable for large LCA problems that, unlike existing approaches, does not make assumptions on model linearity and complexity and includes extensive validation of GSA results. We illustrate the benefits of our protocol by comparing it with an existing method in terms of filtering of noninfluential and ranking of influential uncertainty drivers and include an application example of Swiss household food consumption. We note that our protocol obtains more accurate GSA results, which leads to better understanding of LCA models, and less data collection efforts to achieve more robust estimation of environmental impacts. Implementations supporting this work are available as free and open source Python packages.