Quartz-reinforced polyimide composite is a kind of material with anisotropic and nonuniform properties. The machinability has high dependence on fiber orientation θ. This paper presents the first comprehensive investigation on the cutting model of composites based on fiber orientation. A series of cryogenic cooling milling experiments were carried out to study the influence of fiber orientation on surface morphology, roughness, milling force, and tool wear. The results show that fiber orientation with acute angle has more advantages than obtuse angle. At the same time, it can provide effective chip breaking for latitude and longitude fibers at θ = 45° acute angle. Besides, when the tool is swept 96°, the milling force will reach the maximum, and the shearing effect of the latitude fiber is achieved maximum near θ = 60°. Similarly, the best surface quality is obtained where pits, crack, and burr defects are effectively restrained. Meanwhile, when the chosen cutting speeds are 50, 100, and 150 m/min, the roughness of 0.86 µm, 0.61 µm, 0.5 µm can be attained with θ = 48°, 55°, and 57°, respectively. Although the tool wear is relatively obvious when θ = 60°, the tool is still in a stable wear stage with better machining effect. Hence, it can be concluded that cryogenic cooling machining has better machinability and cutting effect at fiber orientation θ = 60° with larger milling parameters.