The value of propolis is scientifically and commercially measured through the content of biologically active molecules as phenolic compounds and flavonoids; on the other hand, a high percentage of waxes in the propolis composition makes it a substandard beekeeping product. Colombian propolis is characterized by a high content of waxes; however, this drawback turns into an advantage when this material is used for preparing lipid nanocarriers. Accordingly, in this research work, a propolis-extracted material obtained by Randall method is characterized by differential scanning calorimetry, infrared spectroscopy, X-ray diffraction, and 1H-Nuclear Magnetic Resonance. Then, it is used for obtaining nanostructured lipid carriers by the emulsification–diffusion technique, whose recipe and operating work conditions were established by a Plackett–Burman statistical screening design. The obtained particles exhibit sizes less than 300 nm, polydispersity indices around 0.1, zeta potential values less than ±2 mV, good physical stability and they show to be safe in the in vitro irritation test. Thus, Colombian propolis arises as an attractive natural source for obtaining lipid carriers that could be used in pharmaceutical or cosmetic industries for developing innovative products.