(1) Background: Forklifts are used widely in factories, but it shows the problem of large uncertainties when using an RGB-D sensor to recognize and locate pallets in warehouse environments. To enhance the flexibility of current autonomous forklifts in unstructured environments, the improved labeled template matching algorithm was proposed to recognize pallets. (2) Methods: The algorithm comprises four steps: (i) classifying each pixel of a color image with the color feature and obtaining the category matrix; (ii) building a labeled template containing the goods, pallet, and ground category information; (iii) compressing and matching the category matrix and template to determine the region of the pallet; and (iv) extracting the pallet pose from information in respect of the pallet feet. (3) Results: The results show that the proposed algorithm is robust against environmental influences and obstacles and that it can precisely recognize and segment multiple pallets in a warehouse with a 92.6% detection rate. The time consumptions were 72.44, 85.45, 117.63, and 182.84 ms for detection distances of 1000, 2000, 3000, and 4000 mm, respectively. (4) Conclusions: Both static and dynamic experiments were conducted, and the results demonstrate that the detection accuracy is directly related to the detection angle and distance.