Global Optimization (GO) problems occur quite frequently in real-life applications, but are very hard to solve. As a result there is an ever-growing demand to find effective, fast methods for solving GO problems. The goal of this research is to develop algorithms that can quickly find good quality solutions to large-scale nonconvex GO problems, which are the hardest form of GO problems. This research develops a fast heuristic multistart algorithm for solving large-scale GO problems. The new heuristic algorithm, Constraint Consensus Global Optimizer (CCGO), has two phases: global and local. The global phase is an approximate search that quickly explores the variable space using a variety of heuristics. The local phase launches local solvers from the most promising points found in the global phase. CCGO has been specifically designed to utilize the state of the art hardware systems supporting concurrency in software execution. The components of the new heuristic algorithm have been thoroughly examined via a number of experiments. The performance of the new heuristic is then studied with respect to some state of the art complete and heuristic solvers. Empirical results show that the CCGO algorithm has an edge in runtime while offering competitive solution quality. CCGO's ability to find high-quality solutions quickly makes it an attractive choice in both theory and practice: (a) practical applications that need a solution as quickly as possible can use CCGO to get one and (b) optimization solvers that want to capitalize on an early incumbent solution can use CCGO or its approximate search feature within their workflow.