It is a well-known fact that theoretical methodologies play a crucial role to assure an adequate structural assignment of gas-phase clusters. Particularly, in heavy-element containing clusters the inclusion of relativistic effects (scalar and spin-orbit coupling) can significantly affect their chemistry. Therefore, these effects become the keystone on their structural determination. In our work, the way in which relativistic effects were treated, as well as their influence in the process of an adequate identification of lowest-energy isomer (the global minima-"GM"-energy structure), were evaluated in small lead clusters. The potential energy surfaces of small Pbn (n = 3-10) clusters was explored by means of the gradient embedded genetic algorithm program (GEGA). Subsequently, the most stable isomers were re-optimized incorporating relativistic effects through two different approximations: (i) using relativistic effective core potentials (RECPs) or pseudopotentials, which mimics the scalar and spin-orbit coupling relativistic effects (SR and SO) of the core electrons; and (ii) using relativistic Hamiltonians (with proper all-electron basis sets), like, the zeroth-order regular approximation (ZORA) to the Dirac equation, in which the scalar (SR) and spin-orbit coupling (SOC) relativistic effects were also included. The results evidence that methodologies including SOC effect allow to identify the GM energy structure correctly in all the studied cases. Besides, the GEGA algorithm, using a modest RECP, provides good initial structures that become GM after re-optimization at the SOC level.