The precision machining and assembly requirements of poly(p-phenylene-benzobisoxazole) (PBO) fiber-reinforced composites cannot be satisfied using direct integral forming or traditional machining methods. First, we cut PBO fiber-reinforced compositions using different picosecond lasers (with wavelengths of 355 nm and 1030 nm), apply a progressively downshifted focus, and implement multi-pass scanning strategy. The cross-section morphologies of the processed samples were observed using scanning electron microscopy, and the mechanisms of material removal and thermal damage of the materials were analyzed. Finally, the cutting quality and efficiency were related to the laser parameters (laser power, scanning speed and direction, and pulse repetition rate). The UV picosecond laser achieved “cold processing” and a photochemical effect with high cutting quality. The downshift of laser focus with the machining process effectively improved the machining quality and consistency of the material cutting surface. The high-quality and efficient material processing can be achieved with laser power of 8 W, repetition rate of 400 kHz and scanning speed of 1000 mm/s.