This paper presents a new genetic algorithm methodology to solve the trajectory planning problem. This methodology can obtain smooth trajectories for industrial robots in complex environments using a direct method. The algorithm simultaneously creates a collision-free trajectory between initial and final configurations as the robot moves. The presented method deals with the uncertainties associated with the unknown kinematic properties of intermediate via points since they are generated as the algorithm evolves looking for the solution. Additionally, the objective of this algorithm is to minimize the trajectory time, which guides the robot motion. The method has been applied successfully to the PUMA 560 robotic system. Four operational parameters (execution time, computational time, end-effector distance traveled, and significant points distance traveled) have been computed to study and analyze the algorithm efficiency. The experimental results show that the proposed optimization algorithm for the trajectory planning problem of an industrial robot is feasible.