Achieving the ambitious climate change mitigation objectives set by governments worldwide is bound to lead to unprecedented amounts of network investment to accommodate low-carbon sources of energy. Beyond investing in conventional transmission lines, new technologies such as energy storage can improve operational flexibility and assist with the cost-effective integration of renewables. Given the long lifetime of these network assets and their substantial capital cost, it is imperative to decide on their deployment on a long-term cost-benefit basis. However, such an analysis can result in large-scale Mixed Integer Linear Programming (MILP) problems which contain many thousands of continuous and binary variables. Complexity is severely exacerbated by the need to accommodate multiple candidate assets and consider a wide range of exogenous system development scenarios that may occur. In this manuscript we propose a novel, efficient and highly-generalizable framework for solving large-scale planning problems under uncertainty by using a temporal decomposition scheme based on the principles of Nested Benders. The challenges that arise due to the presence of non-sequential investment state equations and sub-problem non-convexity are highlighted and tackled. The substantial computational gains of the proposed method are demonstrated via a case study on the IEEE 118 bus test system that involve planning of multiple transmission and storage assets under long-term uncertainty.