Abstract: Discovering a rare material within a vast search space exhibits a Needle-in-a-Haystack challenge. This challenge of finding a rare material, i.e., the "needle", inside a vast search space, i.e., the "haystack", arises when there is an extreme imbalance of optimum conditions relative to the size of the search space. For example, only 0.82% out of 146k total materials in the open-access Materials Project database have a negative Poisson's ratio, a rare material property. However, current state-of-the-art optimization algorithms are not designed with the capabilities to find solutions to these challenging multidimensional Needle-in-a-Haystack problems, resulting in slow convergence to a global optimum or pigeonholing into a local minimum. In this paper, we present a Zooming Memory-Based Initialization algorithm, entitled ZoMBI, that builds on conventional Bayesian optimization principles to quickly and efficiently optimize Needle-in-a-Haystack problems in both less time and fewer experiments by addressing the common convergence and pigeonholing issues. ZoMBI actively extracts knowledge from the previously best-performing evaluated experiments to iteratively zoom in the sampling search bounds towards the global optimum "needle" and then prunes the memory of low-performing historical experiments to accelerate compute times by reducing the algorithm time complexity from $O(n^3)$ to $O(1)$, as the number of experiments sampled increases. Additionally, ZoMBI implements two custom acquisition functions that use active learning to further guide the sampling of new experiments towards the global optimum. We validate the algorithm's performance on two real-world 5-dimensional Needle-in-a-Haystack material property optimization datasets: discovery of auxetic Poisson's ratio materials and discovery of high thermoelectric figure of merit materials. The ZoMBI algorithm demonstrates compute time speed-ups of 400x compared to traditional Bayesian optimization as well as efficiently discovering materials in under 100 experiments that are up to 3x more highly optimized than those discovered by current state-of-the-art algorithms.