Due to the increase of automation in the field of construction, more and more automation approaches for excavators have been developed. A special case of excavators are drilling excavators. Therefore, a precise pose estimation is an essential task to achieve automation of the drilling process and has not been the subject of interest in research until now. This paper presents a new approach to calculating a pose of the excavator’s undercarriage for a given drilling position. The positioning uses information on the excavator’s workspace considering its kinematics, the terrain, and obstacles at the construction site. Essential to this approach is the computation of the terrain gradient, as well as the computation of the largest inscribed rectangle inside a computed candidate area. Experiments showed that the presented solution yields good results but takes a long time to find them.