Parallelism and Optimization are two disciplines that are used together in numerous applications. Solving complex problems in optimization often means to face complex search landscapes, what needs time-consuming operations. Exact and heuristic techniques are being used nowadays to get solutions to problems in mathematics, logistics, bioinformatics, telecommunications, and many other relevant fields. For these tasks it is mandatory to deal with cluster computing in many cases, multiprocessors, and even with computational grids. In this talk I will address the basic challenges of using parallel tools, software, and hardware for extending existing optimization procedures to work in a parallel environment. I will present some basic optimization algorithms, especially heuristic ones, and discuss the application of parallelism to them. Also, I will show how new techniques become possible due to parallelism, giving birth to a whole new class of algorithms and new research lines.