Successful treatment of skull base tumors with interstitial brachytherapy requires high targeting accuracy for the brachytherapy needles to avoid harming vital anatomical structures. To enable safe placement of the needles in this area, we developed an image-based planning and navigation system for brachytherapy, which includes a custom-made mechanical positioning arm that allows rough and fine adjustment of the needle position. The fine-adjustment mechanism consists of an XYZ microstage at the base of the arm and a needle holder with two fine-adjustable inclinations. The rotation axes of the inclinations cross at the tip of the needle so that the inclinational adjustments do not interfere with the translational adjustments. A vacuum cushion and a noninvasive fixation frame are used for the head immobilization. To avoid mechanical bending of the needles due to the weight of attached tracking markers, which would be detrimental for targeting accuracy, only a single LED marker on the tail of the needle is used. An experimental phantom-based targeting study with this setup demonstrated that a positioning accuracy of 1.4 mm (rms) can be achieved. The study showed that the proposed setup allows brachytherapy needles to be easily aligned and inserted with high targeting accuracy according to a preliminary plan. The achievable accuracy is higher than if the needles are inserted manually. The proposed system can be linked to a standard afterloader and standard dosimetry planning module. The associated additional effort is reasonable for the clinical practice and therefore the proposed procedure provides a promising tool for the safe treatment of tumors in the skull base area.