This paper investigates the effects of fractal parameters on the performance of Mandelbrot fractal patch antennas and a four-band patch antenna is proposed based on the 5th-order Mandelbrot fractal structure. It is found that the antennas can easily acquire a multi-band characteristic by using a high-order structure but the overall size can be relatively small. The proposed antenna can well work at the frequencies of 5.5 GHz, 10.9 GHz, 12.2 GHz and 16.7 GHz, respectively, but only has the size of $30\times 30\times 2$ mm. The simulation results have demonstrated its good performance.